判斷字符串s3是否能由兩個(gè)字符串s1和s2切分拼成，復(fù)雜度O(nm)，空間復(fù)雜度O(m)的寫法參考了Discussion
https://leetcode.com/problems/interleaving-string/solutions/31885/python-dp-solutions-o-m-n-o-n-space-bfs-dfs/
C++版，復(fù)雜度O(nm)，空間復(fù)雜度O(nm)
1 //97
2 //Runtime: 380 ms (Beats 5.2%)
3
4 class Solution {
5 public:
6 int dp[1010][1010];
7
8 bool isInterleave(string s1, string s2, string s3) {
9 if(!s1.length()) return s2 == s3;
10 if(!s2.length()) return s1 == s3;
11 int len = s3.length();
12 if(len != s1.length() + s2.length()) return false;
13 memset(dp, 0, sizeof(dp));
14 dp[0][0] = 1;
15 for(int i = 1; i <= len; ++i) {
16 for(int j = 0; j <= i && j <= s1.length(); ++j) {
17 if(j >= 1 && s1[j - 1] == s3[i - 1] && dp[i - 1][j - 1]) {
18 dp[i][j] = 1;
19 }
20 else if(j >= 0 && j < i && (i - j - 1) < s2.length() && s2[i - j - 1] == s3[i - 1] && dp[i - 1][j]) {
21 dp[i][j] = 1;
22 }
23 if(i == len && dp[i][j]) return true;
24 }
25 }
26 return false;
27 }
28 };
Python版，復(fù)雜度O(nm)，空間復(fù)雜度O(m)（用xrange空間和時(shí)間cost更小）
1 #97
2 #Runtime: 18 ms (Beats 91.39%)
3 #Memory: 13.3 MB (Beats 82.78%)
4
5 class Solution(object):
6 def isInterleave(self, s1, s2, s3):
7 """
8 :type s1: str
9 :type s2: str
10 :type s3: str
11 :rtype: bool
12 """
13 n, m, l = len(s1), len(s2), len(s3)
14 if n + m != l:
15 return False
16 dp = [True for _ in range(m + 1)]
17 for i in xrange(1, m + 1):
18 dp[i] = dp[i - 1] and s2[i - 1] == s3[i - 1]
19 for i in xrange(1, n + 1):
20 dp[0] = dp[0] and s1[i - 1] == s3[i - 1]
21 for j in xrange(1, m + 1):
22 dp[j] = (dp[j] and s1[i - 1] == s3[i + j - 1]) or (dp[j - 1] and s2[j - 1] == s3[i + j - 1])
23 return dp[-1]