Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
判断字符串s3是否能由两个字符串s1和s2切分拼成,复杂度O(nm),空间复杂度O(m)的写法参考了Discussion
https://leetcode.com/problems/interleaving-string/solutions/31885/python-dp-solutions-o-m-n-o-n-space-bfs-dfs/
C++版,复杂度O(nm),空间复杂度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版,复杂度O(nm),空间复杂度O(m)(用xrange空间和时间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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理