思路：
大概思想如下： 1. 动态规划求解，构造dp[][] 二维数组； 2. 设dp[i][j], i 为 第一个字符串的第i个字母；j 为 第二个字符串的第j个字母 3. dp[i][j] 如果为 1 ，表示 s1[i] 等于 s3[i+j] 且 dp[i−1][j] 等于 1，同理s24. 简单的说 dp[i][j] 为 1 就表示这个点可达，以 dp[0][0] 为起点, dp[len1][len2] 为终点，dp数组中值为 1 的点为路径，向下走表示取 s1 的字符，向右走表示取 s2 的字符。这样就将抽象的字符组合转化成了更好理解的二维数组来表示； 5. 最优子结构即为： s1,s2 的 i,j 点字符之前的字符能否交叉组合成字符串 s3 的前 i+j 个字符，转换到二维数组即为，i,j 点左侧点和上方的点是否可达。
private static String solution(String line) { String[] strs = line.split(","); int len0 = strs[0].length(); int len1 = strs[1].length(); int len2 = strs[2].length(); if (len0 + len1 != len2) return false + ""; int dp[][] = new int[len0 + 1][len1 + 1]; // init dp[0][0] = 1; for (int i = 1; i <= len0; i++) { if (strs[0].charAt(i - 1) == strs[2].charAt(i - 1)) dp[i][0] = dp[i - 1][0]; else break; } for (int i = 1; i <= len1; i++) { if (strs[1].charAt(i - 1) == strs[2].charAt(i - 1)) dp[0][i] = dp[0][i - 1]; else break; } for (int i = 1; i <= len0; i++) { for (int j = 1; j <= len1; j++) { int k = i + j; if (strs[0].charAt(i - 1) == strs[2].charAt(k - 1) && dp[i - 1][j] == 1) dp[i][j] = 1; if (strs[1].charAt(j - 1) == strs[2].charAt(k - 1) && dp[i][j - 1] == 1) dp[i][j] = 1; } } if (dp[len0][len1] == 1) return true + ""; return false + ""; }
转载于:https://www.cnblogs.com/ruoh3kou/p/10293091.html
