題意
給出三個字符串s1, s2, s3。求s3是否是s1和s2的interleaving（大概是交織的意思？）。
思路
狀態表示：d[i,j,k]，s10i和s20j是否是s3k的interleaving。且k == i + j。
轉移方程：
以下第三維的k只是為了轉移方程方便看，實際可以不用表示，因為k == i + j。
s1i≠s2j：
? 若s1i==s3k：則d[i,j,k]=d[i?1,j,k?1].
? 若s2j==s3k：則d[i,j,k]=d[i,j?1,k?1].
s1i==s2j：
? d[i,j,k]=d[i?1,j,k?1]||d[i,j?1,k?1].
else
? d[i,j,k]=0.
代碼
const int maxn = 1005;class Solution {public: int d[maxn][maxn]; string S1, S2, S3; int dfs(int i, int j, int k) { if (i < 0) return S2.substr(0, j + 1) == S3.substr(0, k + 1); if (j < 0) return S1.substr(0, i + 1) == S3.substr(0, k + 1); if (d[i][j] != -1) return d[i][j]; if (S1[i] == S2[j]) return d[i][j] = S1[i] == S3[k] ? (dfs(i - 1, j, k - 1) || dfs(i, j - 1, k - 1)) : 0; else { if (S1[i] == S3[k]) return d[i][j] = dfs(i - 1, j, k - 1); if (S2[j] == S3[k]) return d[i][j] = dfs(i, j - 1, k - 1); return d[i][j] = 0; } } bool isInterleave(string s1, string s2, string s3) { memset(d, -1, sizeof(d)); S1 = s1, S2 = s2, S3 = s3; int m = S1.length(), n = S2.length(), l = S3.length(); if (m + n != l) return false; if (!m) return S2 == S3; if (!n) return S1 == S3; return dfs(m - 1, n - 1, l - 1); }};
