LeetMotion
Given three strings s1, s2, and s3, return true if s3 is formed by an interleaving of s1 and s2, or false otherwise.
An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:
s = s1 + s2 + ... + snt = t1 + t2 + ... + tm|n - m| ≤ 1s1 + t1 + s2 + t2 + ... or t1 + s1 + t2 + s2 + ...At each position in s3 we decide: take next char from s1 or from s2? Select an approach:
At each step, we try to match s3[k] (where k = i + j) by taking the next character from either s1[i] or s2[j]. Recurse on both valid choices.
dfs(i, j) — can we form the rest of s3 using s1[i:] and s2[j:]?k == len(s3), return True only if both s1 and s2 are exhausted.def isInterleave(s1, s2, s3): def dfs(i, j): k = i + j if k == len(s3): return i == len(s1) and j == len(s2) if i < len(s1) and s1[i] == s3[k]: if dfs(i+1, j): return True if j < len(s2) and s2[j] == s3[k]: if dfs(i, j+1): return True return False return dfs(0, 0)
The position in s3 is fully determined by k = i + j, so each unique (i, j) state is computed at most once. We cache results in a dictionary dp.
len(s1) + len(s2) ≠ len(s3), return False.(i, j) is already in dp.dp[(i,j)] = result before returning.def isInterleave(s1, s2, s3): if len(s1)+len(s2) != len(s3): return False dp = {} def dfs(i, j): k = i + j if k == len(s3): return i==len(s1) and j==len(s2) if (i,j) in dp: return dp[(i,j)] res = False if i<len(s1) and s1[i]==s3[k]: res = dfs(i+1,j) if not res and j<len(s2) and s2[j]==s3[k]: res = dfs(i,j+1) dp[(i,j)] = res; return res return dfs(0, 0)
Build a 2D table dp[i][j] = can we form s3[i+j:] using s1[i:] and s2[j:]. Fill from bottom-right (dp[m][n] = True) to top-left (dp[0][0]).
(m+1) × (n+1) table initialized to False.dp[m][n] = True (both strings exhausted = empty s3).(i, j): if s1[i] == s3[i+j] and dp[i+1][j], set dp[i][j] = True.dp[0][0].def isInterleave(s1, s2, s3): if len(s1)+len(s2) != len(s3): return False dp = [[False]*(len(s2)+1) for _ in range(len(s1)+1)] dp[len(s1)][len(s2)] = True for i in range(len(s1), -1, -1): for j in range(len(s2), -1, -1): if i<len(s1) and s1[i]==s3[i+j] and dp[i+1][j]: dp[i][j]=True if j<len(s2) and s2[j]==s3[i+j] and dp[i][j+1]: dp[i][j]=True return dp[0][0]
Row i only depends on row i+1 (below) and the current row (rightward). Keep two arrays: dp (previous row) and nextDp (current row). Swap s1/s2 so s2 is always longer → smaller array.
def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m+n != len(s3): return False if n < m: s1,s2 = s2,s1; m,n = n,m dp = [False]*(n+1); dp[n] = True for i in range(m, -1, -1): nextDp = [False]*(n+1) if i == m: nextDp[n] = True for j in range(n, -1, -1): if i<m and s1[i]==s3[i+j] and dp[j]: nextDp[j]=True if j<n and s2[j]==s3[i+j] and nextDp[j+1]: nextDp[j]=True dp = nextDp return dp[0]
Eliminate the second array entirely. A single variable nextDp tracks the right-neighbor value as we sweep j from right to left. Update dp[j] in-place.
def isInterleave(s1, s2, s3): m, n = len(s1), len(s2) if m+n != len(s3): return False if n < m: s1,s2 = s2,s1; m,n = n,m dp = [False]*(n+1); dp[n] = True for i in range(m, -1, -1): nxt = True if i==m else False for j in range(n, -1, -1): res = False if j<n else nxt if i<m and s1[i]==s3[i+j] and dp[j]: res=True if j<n and s2[j]==s3[i+j] and nxt: res=True dp[j]=res; nxt=dp[j] return dp[0]
Discussion
…