DP Solution in Java with induction rule


  • 0
    B
    public class Solution {
        public boolean isInterleave(String s1, String s2, String s3) {
            int len1 = s1.length();
            int len2 = s2.length();
            int len3 = s3.length();
            if (len1 + len2 != len3){
                return false;
            }
            // M[i][j] represents whether we could merge first i char from s1 and first j char from s2 to get first i + j char from s3
            // base case: M[0][0] = true;
            // induction rule : case1 : if s1[i - 1] == s3[i + j - 1], then M[i][j] == M[i][j] || M[i - 1][j] 
            //                  case2 : if s2[j - 1] == s3[i + j - 1], then M[i][j] == M[i][j] || M[i][j - 1]
            boolean[][] M = new boolean[len1 + 1][len2 + 1];
            for (int i = 0 ; i <= len1 ; i++){
                for (int j = 0 ; j <= len2 ; j++){
                    if (i == 0 && j == 0){
                        M[i][j] = true;
                    }
                    if (i >= 1 && s1.charAt(i - 1) == s3.charAt(i + j - 1)){
                        M[i][j] = M[i][j] || M[i - 1][j];
                    }
                    if (j >= 1 && s2.charAt(j - 1) == s3.charAt(i + j - 1)){
                        M[i][j] = M[i][j] || M[i][j - 1];
                    }
                }
            }
            return M[len1][len2];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.