首页 > itarticle > 97. interleaving string 解法

97. interleaving string 解法

admin 11月 12, 2020 0

97. Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

1
2
 
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

1
2
 
Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

解法

  1. DFS/backtracing
1
2
3
4
5
6
7
8
9
10
11
12
 
def (self, s1, s2, s3):
    if len(s1) + len(s2) != len(s3): return False
    def backTrack(i, j, visited):
        if i == len(s1) and j == len(s2): return True
        state = (i, j)
        if state in visited: return False
        k = i + j
        if i < len(s1) and s1[i] == s3[k] and backTrack(i + 1, j, visited): return True
        if j < len(s2) and s2[j] == s3[k] and backTrack(i, j + 1, visited): return True
        visited.add(state); return False
    visited = set()
    return backTrack(0, 0, visited)
  1. BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
class Solution {
public:
    bool (string s1, string s2, string s3) {
        if (s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size(), k = 0;
        unordered_set<int> s;
        queue<int> q{{0}};
        while (!q.empty() && k < n3) {
            int len = q.size();
            for (int t = 0; t < len; ++t) {
                int i = q.front() / n3, j = q.front() % n3; q.pop();
                if (i < n1 && s1[i] == s3[k]) {
                    int key = (i + 1) * n3 + j;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
                if (j < n2 && s2[j] == s3[k]) {
                    int key = i * n3 + j + 1;
                    if (!s.count(key)) {
                        s.insert(key);
                        q.push(key);
                    }
                }
            }
            ++k;
        }
        return !q.empty() && k == n3;
    }
};
  1. DP
    　　dp[i][j]代表s1[:i]和s2[:j]是否是s3[:i+j]的interleaving string
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
class Solution:
    def (self, s1: str, s2: str, s3: str) -> bool:
        L1, L2, L3 = len(s1), len(s2), len(s3)
        if L3 != L1 + L2:
            return False
        dp = [[True for _ in range(L1 + 1)] for _ in range(L2 + 1)]
        for i in range(1, L2 + 1):
            dp[i][0] =  s2[i - 1] == s3[i - 1] and dp[i - 1][0]
        for i in range(1, L1 + 1):
            dp[0][i] =  s1[i - 1] == s3[i - 1] and dp[0][i - 1]
        for i in range(1, L2 + 1):
            for j in range(1, L1 + 1):
                    dp[i][j] = (s3[i + j - 1] == s1[j - 1] and dp[i][j - 1]) or (s3[i + j - 1] == s2[i - 1] and dp[i - 1][j])
        
        #     print(dp[i])
        return dp[L2][L1]

优化： 滚动数组

  1. 特殊解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class Solution:
    def (self, s1: str, s2: str, s3: str) -> bool:
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        i, j, p = 0, 0, 0 # i, j, p are pointers for s1, s2 and s3
        while i >= 0 and j < len(s2):
            if i < len(s1) and s3[p] == s1[i]: # always choose the first string
                i, p = i + 1, p + 1
            elif s3[p] == s2[j]: # if the first string doesn't match, we choose the second string
                j, p = j + 1, p + 1
            else: # if choosing the first string was wrong in previous steps, we retro
                i, j = i - 1, j + 1
        return s1[i:] + s2[j:] == s3[p:] and i >= 0
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能