https://leetcode.com/problems/interleaving-string/
Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2. An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The **interleaving** is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...**Note:** a + b is the concatenation of strings a and b.
Example 1:
Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac” Output: true
Example 2:
Input: s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc” Output: false
Example 3:
Input: s1 = “”, s2 = “”, s3 = "" Output: true
Constraints:
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.
- code
class Solution {
public boolean dfs(String s1, String s2, String s3, int i1, int i2, int i3, int[][] memo){
if (i1 == s1.length()) {
return s2.substring(i2).equals(s3.substring(i3));
}
if (i2 == s2.length()) {
return s1.substring(i1).equals(s3.substring(i3));
}
if (memo[i1][i2] >= 0){
return memo[i1][i2] == 1 ? true : false;
}
if (s1.charAt(i1) == s3.charAt(i3) && dfs(s1, s2, s3, i1 + 1, i2, i3 +1, memo)){
memo[i1][i2] = 1;
return true;
}
if (s2.charAt(i2) == s3.charAt(i3) && dfs(s1, s2, s3, i1, i2 + 1, i3 + 1, memo)){
memo[i1][i2] = 1;
return true;
}
memo[i1][i2] = 0;
return false;
}
public boolean isInterleave(String s1, String s2, String s3) {
if (s1.length() + s2.length() != s3.length()) {
return false;
}
int[][] memo = new int[s1.length()][s2.length()];
for (int i = 0; i < s1.length(); i++){
for (int j = 0; j < s2.length(); j++){
memo[i][j] = -1;
}
}
return dfs(s1, s2, s3, 0, 0, 0, memo);
}
}