Skip to content
BASA DSA

Interleaving String

Medium2-D Dynamic Programming

Return whether s3 can be formed by interleaving all characters of s1 and s2 while preserving each source string order.

Example 1

Input
s1 = "ab"
s2 = "cd"
s3 = "acbd"
Output
true

Explanation

Take a from s1, c from s2, b from s1 and d from s2, preserving each order.

Example 2

Input
s1 = "ab"
s2 = "cd"
s3 = "adbc"
Output
false

Explanation

d would precede c from s2, violating its order.

Example 3

Input
s1 = ""
s2 = ""
s3 = ""
Output
true

Explanation

Two empty sources form the empty target.

Constraints

  • 0 <= len(s1),len(s2) <= 100
  • 0 <= len(s3) <= 200
  • Strings contain lowercase English letters

Function contractisInterleaveArguments: json, json, json
Loading draft…
SolutionRuns on your device