题目: Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:s1 ="aabcc"
,s2 = "dbbca"
, When s3 = "aadbbcbcac"
, return true.
"aadbbbaccc"
, return false. 这个题目值得记录的原因除了自己的解法没有通过大集合以外,主要还在与对动态规划的理解。在这两个月研究算法的过程中,我发现自己更倾向于直观的理解,而抽象思维上相对较弱。我们以这道题做个例子。
直观上,我看到该题,就会去想,s1取一部分,s2取一部分,然后再s1取一部分,反复知道匹配完成s3,算法去模拟这样的操作。
而当s1和s3匹配了一部分的时候,剩下s1‘和剩下的s3‘与s2又是一个子问题。这样很容易写成一个递归,但是需要注意两点:
1. 递归方法中,我们总是拿s1首先去匹配s3,如果不匹配,直接返回false。这样做的原因是保持匹配是“交替”进行的;
2. 当出现既可以匹配s1,又可以匹配s2的时候,一样可以通过递归来解决,看下面的代码。
1 private boolean isInterleaveInternal(String s1, String s2, String s3){ 2 if(s1.equals("")) { 3 return s2.equals("") && s3.equals(""); 4 } 5 if(s1.equals(s3) && s2.endsWith("")) return true; 6 int i1 = 0; 7 int i2 = 0; 8 int i3 = 0; 9 if(s1.charAt(0) != s3.charAt(0)) return false;10 while(i1 < s1.length() && i2 < s2.length() && i3 < s3.length() &&11 s1.charAt(i1) == s3.charAt(i3)) {12 i1++;13 i3++;14 //如果这里s2也可以匹配s3,那么我们立马递归进行匹配15 if(s2.charAt(i2) == s3.charAt(i3) && isInterleaveInternal(s2.substring(i2), s1.substring(i1), s3.substring(i3)))16 return true;17 }18 //接下来开始匹配s219 return isInterleaveInternal(s2, s1.substring(i1), s3.substring(i3));20 21 }
所以在调用这个方法的时候,也比较复杂,需要保证一定是s1首先匹配s3.
1 public boolean isInterleave(String s1, String s2, String s3) { 2 // Start typing your Java solution below 3 // DO NOT write main() function 4 if(s1.length() + s2.length() != s3.length()) return false; 5 if(s1.equals("") || s2.equals("") || s3.equals("")) { 6 if(s3.equals("")) return s1.equals("") && s2.equals(""); 7 else return s1.equals(s3) || s2.equals(s3); 8 } 9 if(s1.charAt(0) == s3.charAt(0)) {10 if(s2.charAt(0) != s3.charAt(0)) {11 return isInterleaveInternal(s1, s2, s3);12 }else {13 if(isInterleaveInternal(s1, s2, s3)) return true;14 else return isInterleaveInternal(s2, s1, s3);15 }16 }else if(s2.charAt(0) == s3.charAt(0)) return isInterleave(s2, s1, s3);17 else return false;18 }
这个办法看上去蛮直观的,是我马上能想到的,而且也是收到的影响。
但是大集合会超时,而且不好的地方是主函数有挺多的条件判断,显得不够简洁。
于是我们参考了这里的方法。
动态规划矩阵matched[l1][l2]表示s1取l1长度(最后一个字母的pos是l1-1),s2取l2长度(最后一个字母的pos是l2-1),是否能匹配s3的l1+12长度。
那么,我们有
matched[l1][l2] = s1[l1-1] == s3[l1+l2-1] && matched[l1-1][l2] || s2[l2 - 1] == s3[l1+l2-1] && matched[l1][l2-1]
边界条件是,其中一个长度为0,另一个去匹配s3.
这里s1和s2交替出现的规律并不明显,所以没有直观地想到。
代码如下:
1 public boolean isInterleave2(String s1, String s2, String s3){ 2 if(s1.length() + s2.length() != s3.length()) return false; 3 boolean[][] matched = new boolean[s1.length() + 1][s2.length() + 1]; 4 matched[0][0] = true; 5 for(int i1 = 1; i1 <= s1.length(); i1++){ 6 if(s3.charAt(i1-1) == s1.charAt(i1-1)) { 7 matched[i1][0] = true; 8 }else break; 9 }10 for(int i2 = 1; i2 <= s2.length(); i2++){11 if(s3.charAt(i2 - 1) == s2.charAt(i2 - 1)) {12 matched[0][i2] = true;13 }else break;14 }15 16 for(int i1 = 1; i1 <= s1.length(); i1++){17 char c1 = s1.charAt(i1 - 1);18 for(int i2 = 1; i2 <= s2.length(); i2++){19 int i3 = i1 + i2;20 char c2 = s2.charAt(i2 - 1);21 char c3 = s3.charAt(i3 - 1);22 if(c1 == c3){23 matched[i1][i2] |= matched[i1 - 1][i2];24 }25 if(c2 == c3){26 matched[i1][i2] |= matched[i1][i2 - 1];27 }28 }29 }30 return matched[s1.length()][s2.length()];31 }
总结下:
1)递归能写出比较清晰简单的代码,但是有比较高的时间复杂度;
2)在递归不满足条件的情况下,动态规划是个比较好的选择;
3)一般来说,独立变量的个数决定动态规划的维度,例如l1和l2独立变化,所以用了二维动态规划。