描述
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
样例
比如 s1 = "aabcc" s2 = "dbbca"
- 当 s3 = "aadbbcbcac"，返回 true.
- 当 s3 = "aadbbbaccc"， 返回 false.
挑战
要求时间复杂度为O(n^2)或者更好
思路
State：
dp[i][j] 表示 A的前i个字符 与 B的前i个字符 能否交替组成 C的前 i+j的字符
Function：
dp[i][j] =
dp[i - 1][j] && (A[i-1] == C[i+j-1]) ||
dp[i][j - 1] && (B[j-1] == C[i+j-1])
Initialization:
dp[0][0] = true;
dp[i][0] = (A[0, 1, ..., i-1] == C[0, 1, ..., i-1])
dp[0][j] = (B[0, 1, ..., i-1] == C[0, 1, ..., i-1])
Answer:
dp[n][m]
代码
class Solution:
"""
@param s1: A string
@param s2: A string
@param s3: A string
@return: Determine whether s3 is formed by interleaving of s1 and s2
"""
def isInterleave(self, s1, s2, s3):
# write your code here
n = len(s1)
m = len(s2)
if n == 0 and m == 0 and len(s3) == 0:
return True
if n+m != len(s3):
return False
dp = [[False for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
if s1[i-1] == s3[i-1]:
dp[i][0] = True
for j in range(1, m+1):
if s2[j-1] == s3[j-1]:
dp[0][j] = True
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = (dp[i-1][j] & (s1[i-1] == s3[i+j-1])) | (dp[i][j-1] & (s2[j-1]== s3[i+j-1]))
return dp[n][m]
题目来源
https://www.lintcode.com/problem/interleaving-string/description
