[LeetCode] – DP – Climbing Stairs

Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Method:

Using DP. The first reaction is recursive, but it exceeds time limit.

Code:

public class Solution {
    public int climbStairs(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2]; 
        }
        
        return dp[n];
    }
}

[LeetCode] – Recursion/ dp- Decode Ways

Problem:

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Method 1: by DP

Consider the current character and the previous character.

Code for method 1:

// dp
public class Solution {
    public int numDecodings(String s) {
        if (s.length() == 0) return 0;
        if (s.charAt(0) == '0') return 0;
        // at least one elements here, and not 0;
        int[] dp = new int[s.length()+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= s.length(); i++){
        
            if(s.charAt(i - 2) > '2' && s.charAt(i-1) == '0'){
                dp[i] = 0;
            }else if (s.charAt(i - 2) > '2' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '1' &&s.charAt(i-1) <= '6' ){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) == '0'){
                dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '7' ){
                dp[i] = dp[i-1];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1]+dp[i-2];
            }else if (s.charAt(i-2) == '1' && s.charAt(i-1) == '0'){
                 dp[i] = dp[i-2];
            }else if (s.charAt(i-2) == '0' && s.charAt(i-1) != '0'){
                dp[i] = dp[i-1];
            }else{
                dp[i] = 0;
            }
        }
        return dp[s.length()];
    }
}

Another more beautiful code for method 1:

public int numDecodings(String s) {  
        if (s.length()==0||s==null||s=="0") 
            return 0; 

        int[] dp = new int[s.length()+1];  
        dp[0] = 1;  
        
        if (isValid(s.substring(0,1)))
            dp[1] = 1;  
        else 
            dp[1] = 0; 
        
        for(int i=2; i<=s.length();i++){  
            if (isValid(s.substring(i-1,i)))  
                dp[i] += dp[i-1];  
            if (isValid(s.substring(i-2,i)))  
                dp[i] += dp[i-2];  
        }  
        return dp[s.length()];  
    }  
      
    public boolean isValid(String s){  
        if (s.charAt(0)=='0') 
            return false;  
        int code = Integer.parseInt(s);  
        return code>=1 && code<=26;  
    }

Method 2: by Recursion. Too slow.

// by recursive
public class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        if (len == 0) return 0;
        if (len == 1 ){
            if (isValid(s.substring(0,1))) return 1;
            else return 0;
        }
        int res = 0;
        // at least have two elements here.
        if (isValid(s.substring(len-1,len))) res += numDecodings(s.substring(0,len-1));
        if (isValid(s.substring(len-2, len))) res += numDecodings(s.substring(0,len-2));

        return res;
    }
    
    public boolean isValid (String s){
        if (s.length() == 0 ) return false;
        int i = Integer.parseInt(s);
        if ( i >= 1 && i <= 26 ) return true;
        else return false;
    }
}

[LeetCode] – Recursion / DP / Greedy – Wildcard Matching

Problem:

Implement wildcard pattern matching with support for '?' and '*'.

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

Reference: http://shmilyaw-hotmail-com.iteye.com/blog/2154716

Method 1:  Greedy

str: the original string we need to examine

pattern: the string with wildcard

s: the cursor in str

p: the cursor in p

StarIdx: the place of the last encountered * (Initialize as -1)

match: the place in str, when p encountered a *

• We go through every char in str
  • If p and s match, p++, s++
  • If p and s do not match, and p encounter a *: remember the current place of p and s in ‘StarIdx’ and ‘match’. Then, p++l .
  • If p and s do not match, and p does not encounter a *, but StarIdx is not  -1: update p as StarIdx+1, update match as match+1, update s as match.
  • If p and s do not match, and p does not currently at a *, and p does not ever encountered an * before, we can decide, the two string do not match. Return false;
• After checking every char in str, we need to check if there are still char left in p. We only allow *.

Code:

public class Solution {
    public boolean isMatch(String str, String pattern) {
        int s = 0; // cursor for traversal in str.
        int p = 0; // cursor for traversal in pattern.
        int starIdx = -1; // once we found a star, we want to record the place of the star.
        int match = 0; // once we found a star, we want to start to match the rest of pattern with str, starting from match; this is for remembering the place where we need to start.
        
        // we check and match every char for str.
        while (s < str.length()){
            // 1. case 1: we are not currently at any *, 
            if (p < pattern.length() && (pattern.charAt(p) == str.charAt(s) || pattern.charAt(p) == '?')){
                p++;
                s++;
            }// 2. case 2: we are currently at a '*'
            else if (p < pattern.length() && pattern.charAt(p) == '*' ){
                starIdx = p;
                p++;
                match = s;
            } // 3. case 3: they do not match, we do not currently at a *, but the last matched is a *
            else if (starIdx != -1){
                match++;
                s = match;
                p = starIdx + 1;
            } // 4. case 4: they do not match, do not currently at a *, and last matched is not a *, then the answer is false;
            else{
                return false;
            }
        }
        // when we finish matching all characters in str, is pattern also finished? we could only allow '*' at the rest of pattern
        while (p < pattern.length() && pattern.charAt(p) == '*')
        p++;
  
        return p == pattern.length();
    }
}

Method 2:

We could use recursive method. Recursive: we just check one step. Iterative: we use while to check all steps.

• Parameters:
  • String str: the original string
  • String pattern: the pattern string
  • int l: the cursor in original string
  • int r: the cursor in pattern string
• Function: starting from l and r, the left part do match.
• Base Case: If r reaches the end of str, we need to check if l also reaches the end of pattern. If so, match.
• Reduction: check the current char in pattern string
  • If regular, just increase l and r by 1;
  • If *, first, go to the last *, and then check if match. (we have to use while loop to find the correct starting point.)

Code for method 2:

public class Solution {
    public boolean isMatch(String s, String p) {
        return helper(s,p,0,0);
        
    }
    
    
    boolean helper(String s, String p, int l, int r) {
           if(r == p.length()) return l == s.length();
           
           if(p.charAt(r) == '*') {
                 while(r < p.length() && p.charAt(r) == '*') r++;   // Move the index at p to a non-start char.
                 while(l < s.length()) {
                     if(helper(s, p, l, r)) return true; // Find one match, return true.
                      l++; // Try the next one.
                  }
                 return helper(s, p, l, r);
            }else if(l < s.length() && (p.charAt(r) == '?' || s.charAt(l) == p.charAt(r))){
                return helper(s, p, l + 1, r + 1);
            }else{
                 return false;
            }
    }

}

Method 3:

However, the recursive method is too slow and we need to have a quicker speed. So we try to solve it by DP.

1. Regular case: if two chars are the same, or p is ‘?’, then go to check dp[i-1][j-1]

2. Special case: when p is ‘*’, we need to check dp[i-1][j-1] for every i>0. If there is one true, then the answer is true.

Code for method 3:

// use DP
public class Solution {
    public boolean isMatch(String s, String p) {
        int width = s.length();
        int height = p.length();
        
        boolean[][] dp = new boolean[width + 1][height + 1];
        dp[0][0] = true;
        
        for (int i = 1; i <= width; i++){
            for (int j = 1; j <= height; j++){
                if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'){
                    dp[i][j] = dp[i-1][j-1];
                }else if (p.charAt(j-1) == '*'){
                    int cur = i;
                    while (cur > 0){
                        if (dp[cur-1][j-1]){
                            dp[i][j]= true;
                            break;
                        }
                        cur--;
                    }
                }
            }
        }
        
        return dp[width][height];
    }
}

[LeetCode] – Recursion / dp – Interleaving String

Problem:

Given s1, s2, s3, 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.

Method 1: (by recursion)

• Recursion method is too slow, and can not pass the checker. But is still a way to approach the problem.
• Several things to remember:
  • We could start from s1 or s2, not necessarily s1.
  • If s1 is null, s2 is null, only when s3 is also null, we get true. Otherwise false;
  • If we go through s1 and s3, try to cut the same part and stop until we reach something different, we might be wrong. Because there may be same sub-string in s2, and the actual choice is s2. So we have to check the answer every time we advance by 1 in s1 and s3. But don’t change s3 and s1.

Code for method 1:

// Recursion
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        return helper(s1, s2, s3) | helper(s2, s1, s3);

    }
    public boolean helper(String s1, String s2, String s3){
        // helper method make sure s1 goes first.
        // Base cases: (make sure that s1 is not null) 
        if (s1.length() == 0 && s2.length() == 0 && s3.length() == 0) return true;
        if (s1.length() == 0 && s2.length() != 0) return false;
       
        int i = 0;
        while (i < s1.length() && i < s3.length() && s1.charAt(i) == s3.charAt(i)){
            i++;
            // check if already true; and do not change s1 and s3.
            if (helper(s2,s1.substring(i),s3.substring(i))) return true;
        }
        if (i == 0) return false;
        s1 = s1.substring(i);
        s3 = s3.substring(i);
        return helper(s2,s1,s3);
    }
}

Method 2: (by dp)

• Remember: “When you see string problem that is about subsequence or matching, dynamic programming method should come to your mind naturally. ”
• dp[i][j] means if the i+j chars in s3 are composed of i chars in s1, and j chars in s2. We just have to check the new added char every time we increase the dp’s dimension.
• Don’t forget to kick out the case that s3 does not include all the chars in s1 and s2.
• One trick for dp: string index is one less than dp matrix index.

Code for method 2:

// by dp
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int height = s1.length();
        int width = s2.length();
        // consider special case: s3 does not include all the elements in s1 and s2.
        if (s3.length() != height+width) return false;
        boolean[][] dp = new boolean[height+1][width+1];
        
        dp[0][0] = true;
        for (int i = 1; i <= height; i++){
            if (s1.charAt(i-1) == s3.charAt(i-1) && dp[i-1][0] ) dp[i][0] = true;
        }
        
        for (int j = 1;j <= width; j++){
            if (s2.charAt(j-1) == s3.charAt(j-1) && dp[0][j-1] ) dp[0][j] = true;
        }
        
        for (int i = 1; i <= height; i++){
            for (int j = 1; j <= width; j++){
                if ((s3.charAt(i+j-1) == s2.charAt(j-1) && dp[i][j-1]) || (s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j])){
                     dp[i][j] = true;
                }
            }
        }
        return dp[height][width];
    }
}

[LeetCode] – Recursion/DP- Regular Expression Matching

Problem:

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Method 1(Recursion):

1. Make sure we totally understand the question.

• “.” is easy, just representing a single char.
• “x*” represent 0 or more x, e.g., “”,”x”,”xx”,”xxx”,”xxxxxx”…

2. We use recursive method. Check if the first part is match or not, if yes, check the rest of the regular expression.

• Reduction:
  • If next char is not “*”, we just compare this current char, and reduce both the length of s and p by 1.
  • If next char is “*”:
    • If the current char is the same, reduce s by 1 and check again. Until the current char is different.  — Not accurate! Consider: “aaa” and “a*a”. So every time before we reduce p by 1, we have to check if they match. This check must to be placed before we reduce p by 1, since we could have the case: s = abc   p = .*abc
    • If the current char is different, reduce p by 2.
• Base case: As reduction reduces length by 1 or 2 every time, we need to consider finally when length == 0 or length == 1.
  • If p.length() == 0, check if s.length() is also 0.
  • If p.length() == 1, check if s.length() is also 1 and the char match or not.
• A detail: s.subString(l), could return null if l is the length of s.
• A detail: always check s.length

Code for method 1:

public class Solution {
    public boolean isMatch(String s, String p) {
        if (p.length() == 0){
            return s.length() == 0;
        }
        if (p.length() == 1){
            return s.length() == 1 && (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.');
        }
        
        // Now, we make sure that p has at least 2 chars.
        if (p.charAt(1) != '*'){
            if (s.length() == 0) return false;
            else return  (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')&& isMatch(s.substring(1), p.substring(1));

        }else{ // p.charAt(1) == '*''
            while (s.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.')){
                if (isMatch(s,p.substring(2))) return true;  // this has to be before s= s.substring(1), to deal with the case: s=abc  p = .*abc
                
                s = s.substring(1);
                
                
            }
            return isMatch(s, p.substring(2));
        }
        
    }
}

Method 2(DP):

1. Create a 2-d matrix, with width as p.length(), height as s.length()

2. Consider an important question: what does ‘a*’ mean?

• Case1: Means nothing, we can’t totally delete ‘a*’. — dp[i][j] = dp[i][j-2]
• Case 2: Means some numbers of ‘a’ in s. — dp[i][j]= dp[i-1][j] (Try to change this case to case 1.)

3. Pay attention to the initialization.  We want to make sure when s is null and p is ‘a*’, we get a ‘true’. This is a base case for Case 1.

Code for method 2:

// Use dp
public class Solution {
    public boolean isMatch(String s, String p) {
       boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
      dp[0][0] = true;
      
      for (int i = 1; i <= p.length(); i++){
          if (p.charAt(i-1) == '*') dp[0][i] = dp[0][i-2];
      }
      
      for (int i = 1; i <= s.length(); i++){
          for (int j = 1; j <= p.length(); j++){
              char pChar = p.charAt(j-1);
              char sChar = s.charAt(i-1);
              
              if (pChar != '*'){
                  if (pChar == sChar || pChar == '.'){
                      dp[i][j] = dp[i-1][j-1];
                  }else{
                      dp[i][j] = false;
                  }
              }else{
                  if (p.charAt(j-2) != sChar && p.charAt(j-2) != '.'){
                      dp[i][j] = dp[i][j-2];
                  }else{
                      dp[i][j] = dp[i-1][j]|dp[i][j-2];
                  }
              }
          }
      }
      
      
      return dp[s.length()][p.length()];
      
    }
}