LC97. Interleaving String

Find whether s3 is formed by the interleaving of s1 and s2.

Posted by freeCookie🍪 on January 12, 2017

LC97. Interleaving String

Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.

For example, Given: s1 = "aabcc", s2 = "dbbca",

When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.

初步的想法是记录每一步可能match的位置,然后backtrack,然后递归… 天啊求实习啊。看了眼discuss 非常简洁的dfs方法, 记录两个字符串匹配到的位置,用带memo的DP存每一步匹配的结果。

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        char[] arr3 = s3.toCharArray();
        if(arr3.length != arr1.length + arr2.length)    return false;
        return isValid(arr1, arr2, arr3, 0, 0, 0, new boolean[arr1.length+1][arr2.length+1]);
      }
      
      // i - c1 pos, j - c2 pos, k - c3 pos
      // inValid[i][j]  cache whether s1[0-i] and s2[0-j] can interleave s3[0-k]
      private boolean isValid(char[] c1, char[] c2, char[] c3, int i, int j, int k, boolean[][] inValid){
          if(inValid[i][j]) return false;
          if(k == c3.length)    return true;
          boolean valid = (i < c1.length && c1[i] == c3[k] && isValid(c1, c2, c3, i+1, j, k+1, inValid)) 
          || (j < c2.length && c2[j] == c3[k] && isValid(c1, c2, c3, i, j+1, k+1, inValid));
          if(!valid)    inValid[i][j] = true;
          return valid;
      }
}

O(m+n), O(mn)大概?

膜拜答主,如此简洁的答案,比我写的bug不知道好了多少…