## Leetcode: interleaved string (Python)

A good function 2020-11-13 02:53:28
leetcode interleaved string python

## 1. Title Description

Given three strings s1, s2, s3, verification s3 Is it by s1 and s2 Interlaced .
Example 1:

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

Example 2:

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

## 2. Ideas

### 2.1 recursive

First check s3 First character of , If it is equal to s1 First character of , And it's not equal to s2 Second character of , take s1 and s3 Move back a bit , recursive . Be equal to s2 The first character of is not equal to and s1 The first character of , take s2 and s3 Move back a bit , recursive . If it is equal to s1 The first character of is equal to s2 First character of , There are two possible situations ,s2 Immobility ,s1 Move one bit backward or s1 Immobility ,s2 Move back a bit .

### Code

``````class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s3) != len(s1) + len(s2):
return False
if s1 == "" and s2 == "" and s3 == "":
return True
if s1 == "":
return s2 == s3
if s2 == "":
return s1 == s3
if s3 == s1 and s3 != s2:
return self.isInterleave(s1[1:],s2,s3[1:])
elif s3 == s2 and s3 != s1:
return self.isInterleave(s1,s2[1:],s3[1:])
elif s3 == s2 and s3 == s1:
return self.isInterleave(s1[1:],s2,s3[1:]) or self.isInterleave(s1,s2[1:],s3[1:])
else:
return False
``````

### 2.2 Dynamic programming

dp[i][j] To express with s1 Before (i+1) and s2 Before (j+1) Characters , in total (i+j+2) Characters , Is it interlaced s3 The prefix of . To find out dp[i][j], We need to consider 2 In this case ：

1. When s1 Of the i Characters and s2 Of the j None of the characters match s3 Of the k Characters , among k=i+j . In this case ,s1 and s2 The prefixes of cannot be interleaved s3 The length is k The prefix of . therefore , We let dp[i][j] by False.
2. s1 Of the i Characters or s2 Of the j Characters can match s3 Of the kk Characters , among k=i+j . Suppose the matching character is x And with the s1 Of the i Characters match , We need to put x In the last position of the formed interleaved string . here , In order for us to make sure that s1 Before (i-1) Characters and s2 Before j Characters can form s3 A prefix of . Allied , If we were to s2 Of the j Characters and s3 Of the k Characters match , We need to make sure that s1 Before i Characters and s2 Before (j-1) Characters can form s3 A prefix of , Let's just let dp[i][j] by True.

### Code

``````class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s3) != len(s1) + len(s2):
return False
dp = [[True for j in range(len(s1)+1)] for i in range(len(s2)+1)]
for i in range(len(s2)+1):
for j in range(len(s1)+1):
if i == 0 and j == 0:
dp[i][j] = True
elif i == 0:
dp[i][j] = dp[i][j-1] and s1[j-1] == s3[j-1]
elif j == 0:
dp[i][j] = dp[i-1][j] and s2[i-1] == s3[i-1]
else:
dp[i][j] = (dp[i-1][j] and s2[i-1] == s3[i+j-1]) or (dp[i][j-1] and s1[j-1] == s3[i+j-1])
return dp[-1][-1]
``````

### Optimize

Like any other dynamic planning , You can still use a one bit array to optimize a two-dimensional array .

### Optimize the code

``````class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s3) != len(s1) + len(s2):
return False
dp = [True for i in range(len(s1)+1)]
for i in range(1,len(s1)+1):
dp[i] = dp[i-1] and s1[i-1] == s3[i-1]
for i in range(len(s2)):
for j in range(len(s1)+1):
if j == 0:
dp[j] = dp[j] and s2[i] == s3[i]
else:
dp[j] = (dp[j-1] and s1[j-1] == s3[i+j]) or (dp[j] and s2[i] == s3[i+j])
return dp[-1]
``````