Interleaving String · 數據結構與算法/leetcode/lintcode題解

# Interleaving String ### Source - leetcode: [Interleaving String | LeetCode OJ](https://leetcode.com/problems/interleaving-string/) - lintcode: [(29) Interleaving String](http://www.lintcode.com/en/problem/interleaving-string/) ~~~ Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2. Example For s1 = "aabcc", s2 = "dbbca" When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false. Challenge O(n2) time or better ~~~ ### 題解1 - bug 題目意思是 s3 是否由 s1 和 s2 交叉構成，不允許跳著從 s1 和 s2 挑選字符。那么直覺上可以對三個字符串設置三個索引，首先從 s3 中依次取字符，然后進入內循環，依次從 s1 和 s2 中取首字符，若能匹配上則進入下一次循環，否則立即返回 false. 我們先看代碼，再分析 bug 之處。 ### Java ~~~ public class Solution { /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true or false. */ public boolean isInterleave(String s1, String s2, String s3) { int len1 = (s1 == null) ? 0 : s1.length(); int len2 = (s2 == null) ? 0 : s2.length(); int len3 = (s3 == null) ? 0 : s3.length(); if (len3 != len1 + len2) return false; int i1 = 0, i2 = 0; for (int i3 = 0; i3 < len3; i3++) { boolean result = false; if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) { i1++; result = true; continue; } if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) { i2++; result = true; continue; } // return instantly if both s1 and s2 can not pair with s3 if (!result) return false; } return true; } } ~~~ ### 源碼分析異常處理部分：首先求得 s1, s2, s3 的字符串長度，隨后用索引 i1, i2, i3 巧妙地避開了繁瑣的 null 檢測。這段代碼能過前面的一部分數據，但在 lintcode 的第15個 test 跪了。不想馬上看以下分析的可以自己先 debug 下。我們可以注意到以上代碼還有一種情況并未考慮到，那就是當 s1[i1] 和 s2[i2] 均和 s3[i3] 相等時，我們可以拿 s1 或者 s2 去匹配，那么問題來了，由于不允許跳著取，那么可能出現在取了 s1 中的字符后，接下來的 s1 和 s2 首字符都無法和 s3 匹配到，因此原本應該返回 true 而現在返回 false. 建議將以上代碼貼到 OJ 上看看測試用例。以上 bug 可以通過加入對 `(s1[i1] == s3[i3]) && (s2[i2] == s3[i3])` 這一特殊情形考慮，即分兩種情況遞歸調用 isInterleave, 只不過 s1, s2, s3 為新生成的字符串。 ### 復雜度分析遍歷一次 s3, 時間復雜度為 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1). ### 題解2 在 `(s1[i1] == s3[i3]) && (s2[i2] == s3[i3])` 時分兩種情況考慮，即讓 s1[i1] 和 s3[i3] 配對或者 s2[i2] 和 s3[i3] 配對，那么嵌套調用時新生成的字符串則分別為 `s1[1+i1:], s2[i2], s3[1+i3:]` 和 `s1[i1:], s2[1+i2], s3[1+i3:]`. 嵌套調用結束后立即返回最終結果，因為遞歸調用時整個結果已經知曉，不立即返回則有可能會產生錯誤結果，遞歸調用并未影響到調用處的 i1 和 i2. ### Python ~~~ class Solution: """ @params s1, s2, s3: Three strings as description. @return: return True if s3 is formed by the interleaving of s1 and s2 or False if not. @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix. """ def isInterleave(self, s1, s2, s3): len1 = 0 if s1 is None else len(s1) len2 = 0 if s2 is None else len(s2) len3 = 0 if s3 is None else len(s3) if len3 != len1 + len2: return False i1, i2 = 0, 0 for i3 in xrange(len(s3)): result = False if (i1 < len1 and s1[i1] == s3[i3]) and \ (i1 < len1 and s1[i1] == s3[i3]): # s1[1+i1:], s2[i2:], s3[1+i3:] case1 = self.isInterleave(s1[1 + i1:], s2[i2:], s3[1 + i3:]) # s1[i1:], s2[1+i2:], s3[1+i3:] case2 = self.isInterleave(s1[i1:], s2[1 + i2:], s3[1 + i3:]) return case1 or case2 if i1 < len1 and s1[i1] == s3[i3]: i1 += 1 result = True continue if i2 < len2 and s2[i2] == s3[i3]: i2 += 1 result = True continue # return instantly if both s1 and s2 can not pair with s3 if not result: return False return True ~~~ ### C++ ~~~ class Solution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ bool isInterleave(string s1, string s2, string s3) { int len1 = s1.size(); int len2 = s2.size(); int len3 = s3.size(); if (len3 != len1 + len2) return false; int i1 = 0, i2 = 0; for (int i3 = 0; i3 < len3; ++i3) { bool result = false; if (i1 < len1 && s1[i1] == s3[i3] && i2 < len2 && s2[i2] == s3[i3]) { // s1[1+i1:], s2[i2:], s3[1+i3:] bool case1 = isInterleave(s1.substr(1 + i1), s2.substr(i2), s3.substr(1 + i3)); // s1[i1:], s2[1+i2:], s3[1+i3:] bool case2 = isInterleave(s1.substr(i1), s2.substr(1 + i2), s3.substr(1 + i3)); // return instantly return case1 || case2; } if (i1 < len1 && s1[i1] == s3[i3]) { i1++; result = true; continue; } if (i2 < len2 && s2[i2] == s3[i3]) { i2++; result = true; continue; } // return instantly if both s1 and s2 can not pair with s3 if (!result) return false; } return true; } }; ~~~ ### Java ~~~ public class Solution { /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true or false. */ public boolean isInterleave(String s1, String s2, String s3) { int len1 = (s1 == null) ? 0 : s1.length(); int len2 = (s2 == null) ? 0 : s2.length(); int len3 = (s3 == null) ? 0 : s3.length(); if (len3 != len1 + len2) return false; int i1 = 0, i2 = 0; for (int i3 = 0; i3 < len3; i3++) { boolean result = false; if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3) && i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) { // s1[1+i1:], s2[i2:], s3[1+i3:] boolean case1 = isInterleave(s1.substring(1 + i1), s2.substring(i2), s3.substring(1 + i3)); // s1[i1:], s2[1+i2:], s3[1+i3:] boolean case2 = isInterleave(s1.substring(i1), s2.substring(1 + i2), s3.substring(1 + i3)); // return instantly return case1 || case2; } if (i1 < len1 && s1.charAt(i1) == s3.charAt(i3)) { i1++; result = true; continue; } if (i2 < len2 && s2.charAt(i2) == s3.charAt(i3)) { i2++; result = true; continue; } // return instantly if both s1 and s2 can not pair with s3 if (!result) return false; } return true; } } ~~~ ### 題解3 - 動態規劃看過題解1 和題解2 的思路后動規的狀態和狀態方程應該就不難推出了。按照經典的序列規劃，不妨假設狀態 f[i1][i2][i3] 為 s1的前i1個字符和 s2的前 i2個字符是否能交叉構成 s3的前 i3個字符，那么根據 s1[i1], s2[i2], s3[i3]的匹配情況可以分為8種情況討論。咋一看這似乎十分麻煩，但實際上我們注意到其實還有一個隱含條件：`len3 == len1 + len2`, 故狀態轉移方程得到大幅簡化。新的狀態可定義為 f[i1][i2], 含義為s1的前`i1`個字符和 s2的前 `i2`個字符是否能交叉構成 s3的前 `i1 + i2` 個字符。根據 `s1[i1] == s3[i3]` 和 `s2[i2] == s3[i3]` 的匹配情況可建立狀態轉移方程為： ~~~ f[i1][i2] = (s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]) || (s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]) ~~~ 這道題的初始化有點 trick, 考慮到空串的可能，需要單獨初始化 `f[*][0]` 和 `f[0][*]`. ### Python ~~~ class Solution: """ @params s1, s2, s3: Three strings as description. @return: return True if s3 is formed by the interleaving of s1 and s2 or False if not. @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix. """ def isInterleave(self, s1, s2, s3): len1 = 0 if s1 is None else len(s1) len2 = 0 if s2 is None else len(s2) len3 = 0 if s3 is None else len(s3) if len3 != len1 + len2: return False f = [[True] * (1 + len2) for i in xrange (1 + len1)] # s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2] for i in xrange(1, 1 + len1): f[i][0] = s1[i - 1] == s3[i - 1] and f[i - 1][0] # s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1] for i in xrange(1, 1 + len2): f[0][i] = s2[i - 1] == s3[i - 1] and f[0][i - 1] # i1 >= 1, i2 >= 1 for i1 in xrange(1, 1 + len1): for i2 in xrange(1, 1 + len2): case1 = s1[i1 - 1] == s3[i1 + i2 - 1] and f[i1 - 1][i2] case2 = s2[i2 - 1] == s3[i1 + i2 - 1] and f[i1][i2 - 1] f[i1][i2] = case1 or case2 return f[len1][len2] ~~~ ### C++ ~~~ class Solution { public: /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true of false. */ bool isInterleave(string s1, string s2, string s3) { int len1 = s1.size(); int len2 = s2.size(); int len3 = s3.size(); if (len3 != len1 + len2) return false; vector<vector<bool> > f(1 + len1, vector<bool>(1 + len2, true)); // s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2] for (int i = 1; i <= len1; ++i) { f[i][0] = s1[i - 1] == s3[i - 1] && f[i - 1][0]; } // s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1] for (int i = 1; i <= len2; ++i) { f[0][i] = s2[i - 1] == s3[i - 1] && f[0][i - 1]; } // i1 >= 1, i2 >= 1 for (int i1 = 1; i1 <= len1; ++i1) { for (int i2 = 1; i2 <= len2; ++i2) { bool case1 = s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2]; bool case2 = s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1]; f[i1][i2] = case1 || case2; } } return f[len1][len2]; } }; ~~~ ### Java ~~~ public class Solution { /** * Determine whether s3 is formed by interleaving of s1 and s2. * @param s1, s2, s3: As description. * @return: true or false. */ public boolean isInterleave(String s1, String s2, String s3) { int len1 = (s1 == null) ? 0 : s1.length(); int len2 = (s2 == null) ? 0 : s2.length(); int len3 = (s3 == null) ? 0 : s3.length(); if (len3 != len1 + len2) return false; boolean [][] f = new boolean[1 + len1][1 + len2]; f[0][0] = true; // s1[i1 - 1] == s3[i1 + i2 - 1] && f[i1 - 1][i2] for (int i = 1; i <= len1; i++) { f[i][0] = s1.charAt(i - 1) == s3.charAt(i - 1) && f[i - 1][0]; } // s2[i2 - 1] == s3[i1 + i2 - 1] && f[i1][i2 - 1] for (int i = 1; i <= len2; i++) { f[0][i] = s2.charAt(i - 1) == s3.charAt(i - 1) && f[0][i - 1]; } // i1 >= 1, i2 >= 1 for (int i1 = 1; i1 <= len1; i1++) { for (int i2 = 1; i2 <= len2; i2++) { boolean case1 = s1.charAt(i1 - 1) == s3.charAt(i1 + i2 - 1) && f[i1 - 1][i2]; boolean case2 = s2.charAt(i2 - 1) == s3.charAt(i1 + i2 - 1) && f[i1][i2 - 1]; f[i1][i2] = case1 || case2; } } return f[len1][len2]; } } ~~~ ### 源碼分析為后面遞推方便，初始化時數組長度多加1，for 循環時需要注意邊界(取到等號)。 ### 復雜度分析雙重 for 循環，時間復雜度為 O(n2)O(n^2)O(n2), 使用了二維矩陣，空間復雜度 O(n2)O(n^2)O(n2). 其中空間復雜度可以優化。 ### Reference - soulmachine 的 Interleaving String 部分 - [Interleaving String 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/interleaving-string/)