原题链接：https://leetcode.com/problems/interleaving-string/?tab=Description 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，s2，s3，求判断s3是否是由s1和s2交叉排列组成的。
首先讲讲我的思路。 最开始，我的思路是：让s3与s1和s2逐一比对，然后位移，如果s3中的字符无法与s1和s2中任一匹配，输出false，如果s3直到最后都能完美匹配s1和s2，输出true。但是这种方法的问题在于，如果s1和s2和s3的某个字符完全相同，那就无法判断究竟应该选择s1的字符位移还是选择s2的字符位移，比如： s1=”aabcd”, s2=”aaaabcd”,s3=”aaaaaabbccdd” s3的第一个字符，s1的第一个字符，s2的第一个字符都是相同的，这个时候究竟选择s1位移还是s2位移，就无从判断了。 我的解决方法是： 一旦碰到三个字符串相同的字符，就记录下接下来这个字符分别在每个字符串从此处开始连续出现的次数，根据之后出现的字符和这些次数判断坐标应该如何移动。但是此时我又碰到了另一个问题，如果s1，s2，s3，在移动完一批相同字符以后紧跟着又出现了相同的字符，那就没办法了。 所以最后只好用动态规划，递归，虽然pass了，但是是在后百分之一。 代码如下：
#include<iostream> #include<string> using namespace std; class Solution { public: int min(int a, int b, int c) { int num = a; if (b < num) num = b; if (c < num) num = c; return num; } bool isInterleave(string s1, string s2, string s3, int i1 = 0, int i2 = 0, int i3 = 0) { while (i3<s3.size()) { if (i1 >= s1.size() && i2 >= s2.size()) return false; else if (i1 >= s1.size() && s2[i2] != s3[i3]) return false; else if (i2 >= s2.size() && s1[i1] != s3[i3]) return false; if (s1[i1] == s2[i2] && s1[i1] == s3[i3]) { int count1 = 1, count2 = 1, count3 = 1; while (i1 + count1 < s1.size() && s1[i1] == s1[i1 + count1]) ++count1; while (i2 + count2 < s2.size() && s2[i2] == s2[i2 + count2]) ++count2; while (i3 + count3 < s3.size() && s3[i3] == s3[i3 + count3]) ++count3; int count = min(count1, count2, count3); if (isInterleave(s1, s2, s3, i1 + count, i2, i3 + count)) return true; else if (isInterleave(s1, s2, s3, i1, i2 + count, i3 + count)) return true; else return false; } else if (i1 < s1.size() && s3[i3] == s1[i1]) ++i1; else if (i2 < s2.size() && s3[i3] == s2[i2]) ++i2; else { return false; } ++i3; } if (i1 == s1.size() && i2 == s2.size()) return true; else return false; } }; int main() { Solution a; string s1 = "aaabcd"; string s2 = "aaabcb"; string s3 = "aaaaababcdbc"; bool out = a.isInterleave(s1, s2, s3); cout << out; getchar(); getchar(); return 0; }看了讨论区大神的代码吓了一跳，这个居然可以用广搜解决，然而我写广搜写了无数遍根本想不到用这个方法解决这个问题。 大体思路是：把s1，s2分别作为一个棋盘的行和列，找到从左上到右下的路径，比如，对s1=”aab”,s2=”abc”来说，棋盘的形态是这样的。
o--a--o--b--o--c--o | | | | a a a a | | | | o--a--o--b--o--c--o | | | | a a a a | | | | o--a--o--b--o--c--o | | | | b b b b | | | | o--a--o--b--o--c--o代码如下：
struct MyPoint { int y, x; //y和x是坐标，从(0,0)开始 bool operator==(const MyPoint &p) const { return p.y == y && p.x == x; }//重载了==运算符 }; namespace std { template <> struct hash<MyPoint> { size_t operator () (const MyPoint &f) const { return (std::hash<int>()(f.x) << 1) ^ std::hash<int>()(f.y); } }; } class Solution { public: bool isInterleave(string s1, string s2, string s3) { if (s1.size() + s2.size() != s3.size()) return false; queue<MyPoint> q; unordered_set<MyPoint> visited; //用以记录当前坐标是否遍历的集合 bool isSuccessful = false; int i = 0; q.push(MyPoint { 0, 0 }); q.push(MyPoint { -1, -1 });//这是为了指示是不是最开始就找不到匹配的点。 while (!(1 == q.size() && -1 == q.front().x)) { auto p = q.front(); q.pop(); if (p.y == s1.size() && p.x == s2.size()) { return true; } if (-1 == p.y) { q.push(p); i++; continue; } if (visited.find(p) != visited.end()) { continue; } visited.insert(p); if (p.y < s1.size()) { // down if (s1[p.y] == s3[i]) { q.push(MyPoint { p.y + 1, p.x }); } } if (p.x < s2.size()) { // right if (s2[p.x] == s3[i]) { q.push(MyPoint { p.y, p.x + 1 }); } } } return false; } };另外还有一种效率次一点的DP算法。DP算法的逻辑其实和迪杰斯特拉有异曲同工之妙，它构建了一个bool型的table，table的长和宽分别是s1和s2的size()。对table中每个点来说，它只关心在在左边和上边的两个点的bool值是不是1，如果它们中有一个是1，那么ok，我们是可以到达这个点的，到了这个点以后再将s1或s2对应的坐标与s3对应的坐标比较，判断这个位置究竟是1还是0，其实也是走迷宫，从左上能走到右下，就说明可行。
bool isInterleave(string s1, string s2, string s3) { if(s3.length() != s1.length() + s2.length()) return false; bool table[s1.length()+1][s2.length()+1]; for(int i=0; i<s1.length()+1; i++) for(int j=0; j< s2.length()+1; j++){ if(i==0 && j==0) table[i][j] = true; else if(i == 0) table[i][j] = ( table[i][j-1] && s2[j-1] == s3[i+j-1]); else if(j == 0) table[i][j] = ( table[i-1][j] && s1[i-1] == s3[i+j-1]); else table[i][j] = (table[i-1][j] && s1[i-1] == s3[i+j-1] ) || (table[i][j-1] && s2[j-1] == s3[i+j-1] ); } return table[s1.length()][s2.length()]; }