高端网站建设赣州,网站建设 网站优化,导购网站怎么做的,wordpress 发布到公网题目
输入3个字符串s1、s2和s3#xff0c;请判断字符串s3能不能由字符串s1和s2交织而成#xff0c;即字符串s3的所有字符都是字符串s1或s2中的字符#xff0c;字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如#xff0c;字符串aadbbcbcac可以由…题目
输入3个字符串s1、s2和s3请判断字符串s3能不能由字符串s1和s2交织而成即字符串s3的所有字符都是字符串s1或s2中的字符字符串s1和s2中的字符都将出现在字符串s3中且相对位置不变。例如字符串aadbbcbcac可以由字符串aabcc和dbbca交织而成。
分析
每步从字符串s1或s2中选出一个字符交织生成字符串s3中的一个字符那么交织生成字符串s3中的所有字符需要多个步骤。每步既可能从字符串s1中选择一个字符也可能从字符串s2中选择一个字符也就是说每步可能面临两个选择。完成一件事情需要多个步骤而且每步都可能面临多个选择这个问题看起来可以用回溯法解决。 这个问题并没有要求列出所有将字符串s1和s2交织得到字符串s3的方法而只是判断能否将字符串s1和s2交织得到字符串s3。如果能够将字符串s1和s2交织得到字符串s3那么将字符串s1和s2交织得到字符串s3的方法的数目大于0。这只是判断问题的解是否存在即判断解的数目是否大于0因此这个问题更适合应用动态规划来解决。 可以用函数fij表示字符串s1的下标从0到i的子字符串记为s1[0…i]长度为i1和字符串s2的下标从0到j的子字符串记为s2[0…j]长度为j1能否交织得到字符串s3的下标从0到ij1记为s3[0…ij1]长度为ij2的子字符串。fm-1n-1就是整个问题的解。 当s3[ij1]和s1[i]相同时fij的值等于fi-1j的值。类似地当s3[ij1]和s2[j]相同时fij的值等于fij-1的值。如果s1[i]和s2[j]都和s3[ij1]相同此时只要fi-1j和fij-1有一个值为true那么fij的值为true。
解
public class Test {public static void main(String[] args) {boolean result isInterleave(aabcc, dbbca, aadbbcbcac);System.out.println(result);}public static boolean isInterleave(String s1, String s2, String s3) {if (s1.length() s2.length() ! s3.length()) {return false;}boolean[][] dp new boolean[s1.length() 1][s2.length() 1];dp[0][0] true;// 列为0没有取用s2字符串的数字for (int i 0; i s1.length(); i) {dp[i 1][0] s1.charAt(i) s3.charAt(i) dp[i][0];}// 行为0没有取用s1字符串的数字for (int j 0; j s2.length(); j) {dp[0][j 1] s2.charAt(j) s3.charAt(j) dp[0][j];}for (int i 0; i s1.length(); i) {for (int j 0; j s2.length(); j) {char ch1 s1.charAt(i);char ch2 s2.charAt(j);char ch3 s3.charAt(i j 1);// 注意是dp[i 1][j 1]dp[i 1][j 1] (ch1 ch3 dp[i][j 1]) || (ch2 ch3 dp[i 1][j]);}}return dp[s1.length()][s2.length()];}
}
