DP in java with explanation


  • 0
    J

    /judge[i][j] means using i characters at the beiginning of s1 and j characters at the beginning
    of s2 and judging if it is interleaving with i+j characters at the beginning of s3
    /
    class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
    int len1 = s1.length(),len2 = s2.length();
    boolean[][] judge = new boolean[len1+1][len2+1];
    judge[0][0] = true;
    if (len1 + len2 != s3.length()) {
    return false;
    }
    for (int i = 0;i <= len1;i ++) {
    if(i > 0)
    //judge[0][0] has been declared true
    judge[i][0] = s1.charAt(i-1) == s3.charAt(i-1) &&judge[i-1][0];
    for (int j = 1;j <= len2;j ++) {
    if (s2.charAt(j-1) == s3.charAt(i+j-1)) {
    //if it is true,then refering to judge[i][j-1]
    judge[i][j] = judge[i][j-1];
    }
    if (i > 0 && s1.charAt(i-1) == s3.charAt(i+j-1)) {
    /if it is true,then refering to judge[i-1][j].However,if s2.charAt(j-1) == s3.charAt(i+j-1)
    is also true,then it should be refered to judge[i][j-1],too.
    /
    judge[i][j] = judge[i-1][j] || judge[i][j];
    }
    if(s2.charAt(j-1) != s3.charAt(i+j-1) && i > 0 && s1.charAt(i-1) != s3.charAt(i+j-1)) {
    judge[i][j] = false;
    }
    }
    }
    return judge[len1][len2];
    }
    }


Log in to reply
 

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