Interleaving
String:
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.
When s3 = "aadbbbaccc",
return false.
试了下跟归并一样的贪心思路,果然是不行的,比如 s1= "aa", s2="ab", s3="aaba" 贪心就不行,因为在s1[i] ,s2[j] 都和s3中字母相等的时候,你不知道应该用哪一个。
那就老老实实DP吧,下面空间还可以优化成O(n)的。
class Solution {
public:
bool isInterleave(string s1, strin......
阅读全文