Define dp[i][j] as whether s3[0..i+j-1] can be composed by interleaving the first i characters of s1 with the first j characters of s2.

Interleaving String

hard

Acceptance: 39%

Dynamic Programming

Three strings s1, s2, and s3 are given. Determine whether s3 can be formed by interweaving the characters of s1 and s2, maintaining each string's internal character order but allowing characters from either string at each position.

Examples

Example 1:

Input:s1 = "xy", s2 = "ab", s3 = "xayb"

Output:true

Explanation: Taking x from s1, a from s2, y from s1, b from s2 produces xayb.

Example 2:

Input:s1 = "xy", s2 = "ab", s3 = "xyba"

Output:false

Explanation: No interleaving of 'xy' and 'ab' can produce 'xyba' because 'b' must come before 'a' in s2.

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Interleaving String

Examples

Hints

Related Problems