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(n^2) time or better
解题思路:
s3的第一个字符分别和s1,s2的第一个字符做比较,如果其中一个相同,则去除s3和具有相同前缀的字符串的第一个字符。继续下一轮的比较。最发麻的问题出现了,如果s1和s2的前缀相同,那么选择那个字符串继续比较呢?
这是一个典型的动态规划......
阅读全文