Interleaving String
MediumDynamic Programming · NVIDIA
You are given three strings s1, s2 and s3. Return True if s3 can be built by interleaving s1 and s2, and False otherwise.
Interleaving means repeatedly taking the next unused character from either s1 or s2 and appending it to the result, until both are used up. Every character of s1 and s2 is used exactly once, and the characters of each string keep their original relative order. You may switch between the two strings as often as you like.
Example 1
- Input:
- s1 = "abc", s2 = "def", s3 = "adbcef"
- Output:
- True
- Explanation
- Take
afroms1,dfroms2,bandcfroms1, theneandffroms2. Each source is read in its own order.
Example 2
- Input:
- s1 = "abc", s2 = "def", s3 = "abdfec"
- Output:
- False
- Explanation
s3has the right letters, butfcomes beforee, while ins2theemust come first.
Example 3
- Input:
- s1 = "aa", s2 = "ab", s3 = "aaba"
- Output:
- True
- Explanation
- Taking both
as froms1first gets stuck atb. Instead takeafroms1, thenaandbfroms2, then the lastafroms1. Greedy choices can fail, so all options must be considered.
Constraints
- 0 ≤
s1.length,s2.length≤ 100 - 0 ≤
s3.length≤ 200 s1,s2ands3consist of lowercase English letters