Leetcode–Distinct Subsequences

The Problem:

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit", T = "rabbit"

Return 3.

Notes:

  1. Here when seeing only required to return the number of ways (not the entire list of ways), we could consider DP instead of pure recursion. use match[i][j] to represent number of distinct sub sequence that S[0-i] has for T[0-j] seems a good start.
  2. As for the recurrence formula, if S[i]!=T[j], then simply means S[i] is not used for the match (match[i][j] = match[i-1][j]).  if(S[i]=T[j]), then we can consider the number of ways comes from two paths: use S[i]  (match[i][j] = match[i-1][j-1]); and  not use S[i]  (match[i][j] = match[i-1][j]).
  3. Watch out for the details and edge cases.

Java Solution

public class Solution {
    public int numDistinct(String S, String T) {
        int slen = S.length();
        int tlen = T.length();
        // check length
        if(slen==0 || slen < tlen)
            return 0;
        if(tlen==0)
            return 1;
        // record dist. subseqs of t[0-j] in in s[0-i] in match[i][j]
        int[][] match = new int[slen][tlen];       
        for(int i = 0; i < slen; i++){
            for(int j = 0; j < tlen; j++){
                if(i < j)
                    match[i][j] = 0;
                else if(i==0 && j==0){
                    match[i][j] = S.charAt(0)==T.charAt(0)? 1:0;
                }
                else if(S.charAt(i)==T.charAt(j)){
                    //divide case by either use s[i] or not
                    // only consider j=0 case, i=0 already covered in previous conditions: 
                     //1. i<j  2. i==0&& j==0
                    if(j==0)
                        match[i][j] = match[i-1][j]+1;
                    else
                        match[i][j] = match[i-1][j-1] + match[i-1][j];
                }
                else{
                    match[i][j] = match[i-1][j];
                }
            }
        }
        return match[slen-1][tlen-1];
    }
}
Advertisements

Leetcode–Interleaving String

The 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.

Notes:

  1. I tried recursion first and it exceeds time limit. And for recursion, one immediate optimization is consider if DP could save some duplicate recursion branches.
  2. As for the recursive formulation, We dont need exact detail of which character in s1/s2 match to which character in s3. Instead we only care about if (part of) s1 and (part of) s2 interleave can match (part of) s3. one smart way is to record match[i][j] as “first i characters in s1 and first j characters in s2 can interleave to first i+j characters in s3”.
  3. Watch out for details:
    1. Here we have index of match represent the number of characters in s1/s2, aka. index+1. The reason to do it this way is to represent the situation of “using none of characters from s1/s2”, which cannot use match[0][j] if 0 is the index
    2. As a result of the shift mentioned above, the start/end condition of for loop, and the index in if condition, all needs to be carefully adjusted accordingly.

Java Solution

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int n1 = s1.length();
        int n2 = s2.length();
        int n3 = s3.length();
        if(n1==0)
            return s2.equals(s3);
        if(n2==0)
            return s1.equals(s3);
        if(n1 + n2 != n3 || !sameChar(s1+s2, s3))
            return false;
        //match[i+1][j+1] means s1[0~i] and s2[0~j] can form s3[0~i+j]
        boolean[][] match = new boolean[n1+1][n2+1];
        //start from 1 to avoid mismatch like s1[0]+s2[0]->s3[1]
        for(int i = 0; i <=n1; i++){
            for(int j = 0; j <= n2; j++){
                if(i==0 && j==0)
                    match[i][j] = true;
                else if((i > 0 && s1.charAt(i-1)==s3.charAt(i+j-1) && match[i-1][j])||
                    (j>0 && s2.charAt(j-1)==s3.charAt(i+j-1) && match[i][j-1]))
                    match[i][j] = true;
                else
                    match[i][j] = false;
            }
        }
        
        return match[n1][n2];
    }
    
    public boolean sameChar(String s1, String s2){
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        return new String(ch1).equals(new String(ch2));
    }
}

Leetcode–Decode Ways

The 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.

Notes:

  1. A DP problem. An important observation is that for multi-way sequences  such as  ‘1”2’, the regression function is ways[i] = ways[i-1] + ways[i-2]
  2. Watch out for details:
    1. ‘0’ can only pair with previous ‘1’ or ‘2’, which means ways[i] = ways[i-2]
    2. when using ways[i-2] need to check the bounds

Java Solution

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if(n==0)return 0;
        int[] ways = new int[n];
        if(s.charAt(0)=='0')
            return 0;
        else
            ways[0] = 1;
            
        for(int i = 1; i < n; i++){
            if(s.charAt(i)=='0'){ // only valid if previous is 1 or 2
                if(s.charAt(i-1)=='2'||s.charAt(i-1)=='1'){
                    ways[i] = i>=2 ? ways[i-2]:1;
                }
                else
                    return 0;
            }
            else{
                if(isValid(s.charAt(i-1), s.charAt(i))){
                    // have multiple ways
                    ways[i] = i>=2 ? ways[i-1]+ways[i-2] : 2;
                }
                else{
                    ways[i] =ways[i-1];
                }
            }
        }
        return ways[n-1];
    }
    
    private boolean isValid(char a, char b){
        if(a=='1')
            return true;
        if(a=='2' && b <= '6')
            return true;
        return false;
    }
}

Leetcode–Maximal Rectangle

The Problem:

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Notes:

  1. A DP problem, think of handle each row/column first, get the max length for that row/column, and store it in a 2d array.
  2. Another thing worth mentioning is in the second round, for each non-zero grid should consider a new sequence start from this index since the minrow will change.

Java Solution

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0 || matrix[0].length==0)return 0;
        int n = matrix.length;
        int m = matrix[0].length;
        int[][] area = new int[n][m];
        for(int j = 0; j <m; j++){
            area[0][j] = matrix[0][j]=='0'?0:1;
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                if(matrix[i][j]=='0'){
                    area[i][j]=0;
                }
                else{
                    area[i][j] = area[i-1][j]+1;
                }
            }
        }
        int maxarea = 0;
        int minrow;
        for(int i = 0; i < n; i++){
            for(int j=0; j<m;j++){
                if(area[i][j]!=0){
                    minrow= area[i][j];
                    maxarea = Math.max(maxarea,area[i][j]);
                    // from each nonzero grid, start a new try, because min can change
                    for(int k = j+1; k < m; k++){
                        if(area[i][k]==0)
                            break;
                        minrow = Math.min(area[i][k], minrow);
                        maxarea = Math.max(maxarea, minrow * (k-j+1));
                    }
                }
            }
        }
        return maxarea;
    }
}

Leetcode–Edit Distance

The Problem:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.
  2. Note that the index in the DP array is shifted.

Java Solution

public class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        if(n1==0) return n2;
        if(n2==0) return n1;
        
        int[][] dist = new int[n1+1][n2+1];
        // so here index 0 for dist means zero character, not first character
        for(int i = 0; i <= n1; i++){
            for(int j = 0; j<= n2; j++){
                if(i==0 && j==0)
                    dist[i][j] = 0;
                else if(i==0)
                    dist[i][j] = j;
                else if(j==0)
                    dist[i][j] = i;
                else{
                    int d=0;
                    if(word1.charAt(i-1)!=word2.charAt(j-1)){
                        d = 1;
                    }
                    // from i-1, j-1 by replace or no extra step
                    // from i-1, j by insert
                    // from i, j-1 by delete
                    dist[i][j] =  Math.min(Math.min(dist[i-1][j]+1, dist[i-1][j-1]+d),dist[i][j-1]+1);
                }               
            }
        }
        return dist[n1][n2];
    }
}

Leetcode–Climbing Stairs

The 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?

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.

Java Solution

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

Leetcode–Minimum Path Sum

The Problem:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Notes:

  1. A basic DP problem, use the exact same approach as in Unique Path.

Java Solution

public class Solution {
    public int minPathSum(int[][] grid) {
        if(grid.length==0 || grid[0].length==0)return 0;
        int m = grid.length;
        int n = grid[0].length;
        int[][] path = new int[m][n];
        path[0][0] = grid[0][0];
        for(int i = 1; i < m; i++){
            path[i][0] = path[i-1][0]+grid[i][0];
        }
        for(int j = 1; j < n; j++){
            path[0][j] = path[0][j-1] + grid[0][j];
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                path[i][j] = Math.min(path[i-1][j], path[i][j-1]) + grid[i][j];
            }
        }
        return path[m-1][n-1];
        
    }
}