Decode ways

class Solution {
    public int numDecodings(String s) {

        int len = s.length();
        if (len == 0) return 0;

        int[] ways = new int[len+1];

        // way[n] 表示 这n个数字可以有多少ways
        // idx:   0, 1, 2, 3
        // input:    1, 7, 4
        // f(n) = f(n - 1) when substring(n-1, n) not 0 + f(n - 2) when substring(n-2, n) is valid
        // f(3) = f(2) when ("4") is not 0 + f(1) when ("74") is valid
        ways[0] = 1;
        for (int i = 1; i <= len; i++) {

            // current case can not be 0
            if (s.charAt(i-1) != '0')            
                ways[i] += ways[i - 1];
            if (i >= 2) {
                int num = (s.charAt(i-2) - '0') * 10 + s.charAt(i-1) - '0';
                if (num >= 10 && num <= 26) 
                    ways[i] += ways[i - 2];
            }            
        }

        return ways[len];        
    }
}

Decode ways ii

Wildcard Matching

class Solution {
    public boolean isMatch(String s, String p) {

        int i = 0;
        int j = 0;
        int lastStarIdx = -1;
        int lastMatch = 0;

        while (i < s.length()) {
            // "?" or match, advancing both pointers 
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                i++;
                j++;
            // '*', only advancing j    
            } else if (j < p.length() && p.charAt(j) == '*') {
                lastMatch = i;
                lastStarIdx = j;                
                j++;
            // when prev is * && curr is not '*' && no match, j go back to the last * + 1, s use match++     
            } else if (lastStarIdx != -1) {
                j = lastStarIdx + 1;
                lastMatch++;
                i = lastMatch;
            } else {
                return false;
            }
        }

        // check the rest pattern
        while (j < p.length() && p.charAt(j) == '*') {
            j++;
        }

        return j == p.length();

    }
}

• dp
• similar to edit distance

class Solution {
    public boolean isMatch(String s, String p) {

        int m = s.length(), n = p.length();
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];                
        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (pc[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pc[j - 1] == '?' || pc[j - 1] == sc[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = false;
                }
            }
        }

        return dp[m][n];        
    }
}

Regular expression matching

• '*' can clear previous match
• isMatch("aab", "c*a*b") → true
• 1, If p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]; 2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1]; 3, If p.charAt(j) == '*': here are two sub conditions:

             1   if p.charAt\(j-1\) != s.charAt\(i\) : dp\[i\]\[j\] = dp\[i\]\[j-2\]  //in this case, a\* only counts as empty
             2   if p.charAt\(i-1\) == s.charAt\(i\) or p.charAt\(i-1\) == '.':
                            dp\[i\]\[j\] = dp\[i-1\]\[j\]    //in this case, a\* counts as multiple a 
                         or dp\[i\]\[j\] = dp\[i\]\[j-1\]   // in this case, a\* counts as single a
                         or dp\[i\]\[j\] = dp\[i\]\[j-2\]   // in this case, a\* counts as empty
  

class Solution {
    public boolean isMatch(String s, String p) {

        int m = s.length(), n = p.length();
        char[] sc = s.toCharArray();
        char[] pc = p.toCharArray();
        boolean[][] dp = new boolean[m + 1][n + 1];                
        dp[0][0] = true;

        for (int j = 1; j <= n; j++) {
            if (pc[j - 1] == '*') {
                dp[0][j] = dp[0][j - 2];    // notice: here is -2
            }
        }
        // for (int i = 0; i < p.length(); i++) {
        //     if (p.charAt(i) == '*' && dp[0][i-1]) {
        //         dp[0][i+1] = true;
        //     }
        // }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }                                 

                if (pc[j - 1] == '*') {
                    if (pc[j - 2] == '.' || pc[j - 2] == sc[i - 1]) {
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 1] || dp[i][j-2];    
                    } else {
                        dp[i][j] = dp[i][j-2];
                    }                    
                } 
            }
        }

        return dp[m][n];        
    }
}