#97

Interleaving String

specialist · 960 · lc medium +32 · verified · 43.6% accepted · 8,813 likes · top 25%

⚑ String Matching DP (LCS / Edit Distance)

Description

Determine whether s3 is an interleaving of s1 and s2. An interleaving merges the characters of both strings while preserving the relative character order within each.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

Output: true

Explanation: One way to obtain s3 is:

Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".

Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"

Output: false

Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""

Output: true

Code

1

2

3

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool: