Skip to content

Instantly share code, notes, and snippets.

@toliuweijing
Created August 4, 2013 21:38
Show Gist options
  • Save toliuweijing/6152058 to your computer and use it in GitHub Desktop.
Save toliuweijing/6152058 to your computer and use it in GitHub Desktop.
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if (s1.size() + s2.size() != s3.size()) return false;
bool dp[s1.size()+1][s2.size()+1];
for (int len1 = 0 ; len1 <= s1.size() ; len1++) {
for (int len2 = 0 ; len2 <= s2.size() ; len2++) {
if (len1 == 0 && len2 == 0) { dp[0][0] = true; continue; }
dp[len1][len2] = false;
if (len1 != 0)
dp[len1][len2] |= (s1[len1-1] == s3[len1+len2-1] && dp[len1-1][len2]);
if (len2 != 0)
dp[len1][len2] |= (s2[len2-1] == s3[len1+len2-1] && dp[len1][len2-1]);
}
}
return dp[s1.size()][s2.size()];
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment