[Leetcode] Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

I use this problem to check the implementation of Rabin-Karp algorithm in the last post. A thing need to pay attention is overflow, we could use a smaller prime or we use long to store the hash number.

    public String strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        if(n < m)
            return null;
        int h1 = 0, h2 = 0, h = 1;
        int d = 256, q = 9973;
        
        for(int i = 0; i < m-1; i++)
            h = (h * d) % q;
        for(int i = 0; i < m; i++) {
            h1 = (h1 * d + haystack.charAt(i)) % q;
            h2 = (h2 * d + needle.charAt(i)) % q;
        }
        
        for(int i = 0; i <= n-m; i++) {
            if(h1 == h2) {
                boolean flag = true;
                for(int j = 0; j < m; j++) {
                    if(haystack.charAt(i+j) != needle.charAt(j)) {
                        flag = false;
                        break;
                    }
                }
                if(flag == true)
                    return haystack.substring(i);
            }
            else {
                if(i < n-m) {
                    h1 = ((h1 - haystack.charAt(i) * h) * d + haystack.charAt(i+m)) % q;
                }
                if(h1 < 0)
                    h1 = h1 + q;
            }
        }
        
        return null;
    }

[Algorithm] Rabin-Karp Algorithm

Given a String S and a String P, assume the length of S is larger than P, find the first occurrence of P in S.

This is a very classical problem, a very naive method is just to from S[0] to S[n-m], we check each substring if it is the same with P, the time complexity is O(mn). Another method is called KMP algorithm and it has better time complexity O(n+m), but the coding complexity is quite high. Rabin-Karp is a quite easy algorithm and its average running time is O(m+n).

The core idea is HASH. It also sweep from S[0] to S[n-m], however, it improves the process of checking if the substring S[i...i+m] is the same with P by per-compute a hash for P and the substring. If the hash is not the same, then we are sure that the two string could not be the same, if they are the same, then we check if the two string is the same. The hash code of S[i...i+m-1]is compute as

hash = (S[m-1+i]*d^0 + S[m-2+i]*d^1 + ... + S[i]*d^(m-1)) mod q, here q is prime

Then, we could quick recompute the hash code of S[i+1...i+m] as

new_hash = ((hash - S[i]*d^(m-1)) * d + S[i+m]) mod q

This technique is called rolling hash. In this way we could re-compute the new hash based on the old one in O(1) time.

Below is my implement of the Rabin-Karp, if there is mistake, please contact me

import java.util.*;
 public class Rabin_karp {
 public static int search(String S, String P) {
  int n = S.length();
  int m = P.length();
  if(n < m)
   return -1;

  int h1 = 0; // hash number of String S
  int h2 = 0; // hash number of String P
  int d = 256;
  int h = 1;
  int q = 9973;

  // the value of h would be "pow(d, M-1) % q"
  for(int i = 0; i < m-1; i++) {
   h = (h * d) % q;
  }

  for(int i = 0; i < m; i++) {
   h1 = (h1 * d + S.charAt(i)) % q;
   h2 = (h2 * d + P.charAt(i)) % q;
  }
  System.out.println(h2);
  for(int i = 0; i <= n-m; i++) {
   System.out.println(S.substring(i, i+m) + " " + h1);
   if(h1 == h2) {
    boolean find = true;
    for(int j = 0; j < m; j++) {
     if(S.charAt(i+j) != P.charAt(j)) {
      find = false;
      break;
     }
    }
    if(find == true)
     return i;
   }
   else {
    if(i < n - m)
     h1 = (d * (h1 - h * S.charAt(i)) + S.charAt(i + m)) % q;
    if(h1 < 0)
     h1 = h1 + q;
   }
  }

  return -1;
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   String s = scan.next();
   String p = scan.next();
   System.out.println(search(s, p));
  }
 }
}

Reference: http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/

[Leetcode] Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

The naive method is to sort the array, however, this would not meet the requirement of O(n) time complexity. So, I use a HashMap to hold each element and the max length from this element to the ones smaller than it. Assume that we have arrived at i, and we found A[i]-1 is visited and has a record, thus we don't need to check all the element one by one, we just add A[i]-1's record to one and this would be the longest possible consecutive sequence from A[i]. The total access of each record should not more than 2N. So we could meet the time complexity.

    public int longestConsecutive(int[] num) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int n = num.length;
        for(int i = 0; i < n; i++)
            if(map.containsKey(num[i]) == false)
                map.put(num[i], 0);
        for(int i = 0; i < n; i++)
            if(map.get(num[i]) == 0)
                dfs(num[i], map);
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            result = Math.max(result, map.get(num[i]));
        }
        return result;
    }
    
    private int dfs(int num, HashMap<Integer, Integer> map) {
        if(map.get(num) != 0)
            return map.get(num);
        if(map.containsKey(num-1) == true) {
            map.put(num, dfs(num-1, map) + 1);
        }
        else
            map.put(num, 1);
        return map.get(num);
    }

Another way is to expand a element to its right and left, like finding a connective component, and since connective component has some property as a set, we do not need to check other element in the same component, thus remove them from the set. In such a way, each element is at most visited once and all the operation needed is O(1), thus we could guarantee the time complexity to be O(n).

    public int longestConsecutive(int[] num) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < num.length; i++)
            set.add(num[i]);
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < num.length; i++) {
            int left = num[i] - 1;
            int right = num[i] + 1;
            int count = 1;
            while(set.contains(left) == true) {
                count++;
                set.remove(left);
                left--;
            }
            while(set.contains(right) == true) {
                count++;
                set.remove(right);
                right++;
            }
            result = Math.max(result, count);
        }
        return result;
    }

[Leetcode] Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

The key point is the same with here, try to identify the monotonic part of the array. However, since we have duplicate in array now, we may have the situation that A[mid] is the same with current interval's left-most and right-most element. In such case, we just need to shrink the interval by one, and continue on this new interval.

    public boolean search(int[] A, int target) {
        int n = A.length;
        if(n == 0)
            return false;
        int l = 0, r = n-1;
        while(l <= r) {
            int mid = l + (r-l)/2;
            if(A[mid] == target)
                return true;
            if(A[mid] == A[l]) {
                l++; continue;
            }
            if(A[mid] == A[r]) {
                r--; continue;
            }
            if(A[mid] > A[l]) {
                if(target >= A[l] && target < A[mid])
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            else if(A[mid] < A[r]) {
                if(target <= A[r] && target > A[mid])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
        }
        return false;
    }

[Leetcode] Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

The same idea with the former one, also use two pointer, and sweep all duplicate elements, use a count to check if we have duplicate, if we have, then just make a copy of that duplicate.

    public int removeDuplicates(int[] A) {
        int n = A.length;
        if(n < 3)
            return n;
        int p1 = 0, p2 = 1;
        
        while(p2 < n) {
            int cnt = 1;
            while(p2 < n && A[p2] == A[p1]) {
                p2++; cnt++;
            }
            if(cnt >= 2) {
                p1++;
                A[p1] = A[p1-1];
            }
            if(p2 == n) break;
            p1++;
            A[p1] = A[p2];
            p2++;
        }
        
        return p1+1;
    }

[Leetcode] Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Pointer problem, array in place operation. Use two pointer to indicate the end of non-duplicate array and where we have checked.

    public int removeDuplicates(int[] A) {
        int n = A.length;
        if(n == 0 || n == 1)
            return n;
        int p1 = 0, p2 = 1;
        while(p2 < n) {
            while(p2 < n && A[p2] == A[p1])
                p2++;
            if(p2 == n) break;
            p1++;
            A[p1] = A[p2];
            p2++;
        }
        return p1+1;
    }

[Leetcode] Wildcard Matching

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

At first, I used KMP with '?' and greedy method to solve this problem, the code is very hard to write. Later, I found that we can use recursion to write the code, but I think the code is a little bit difficult to understand. At last, I tried use dp to solve this problem, but I got TLE many times on big data. After checking other's solution, I found that adding a pruning could considerably improve the performance. The key point is as follow:

1. we use dp[i][j] to represent if s[0...i-1] and p[0...j-1] could match or not, here I add an additional row and column in dp to represent null string to ease some case.
2. if s[i-1] == p[j-1] or p[j-1] == '?', then as long as dp[i-1][j-1] == true, dp[i][j] is true else is false
3. the most difficult part is when p[j-1] = '*', we could match it with nothing, then the result would be the same with dp[i][j-1], or we could match it with s[i-1], wich the result would be the same with dp[i-1][j-1], or we could match it multi characters, which is given by dp[i-1][j], here dp[i-1][j] have contains all possible multi matching.

We add an O(n) pruning before we start dp, we count the non '*' character in p, if the number of non '*' is greater than the length of s, then we definitely could not get a match!

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        
        int cnt = 0;
        for(int i = 0; i < n; i++) 
            cnt = cnt + (p.charAt(i) == '*' ? 0 : 1);
        if(cnt > m) return false;
        
        boolean[][] dp = new boolean[m+1][n+1];
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0)
                    dp[i][j] = true;
                else if(i == 0 && j != 0) {
                    if(dp[i][j-1] && p.charAt(j-1) == '*')
                        dp[i][j] = true;
                }
                else if(i != 0 && j == 0)
                    dp[i][j] = false;
                else {
                    if(dp[i-1][j-1] && (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?'))
                        dp[i][j] = true;
                    else if(p.charAt(j-1) == '*')
                        dp[i][j] = dp[i-1][j] || dp[i-1][j-1] || dp[i][j-1];
                    else 
                        dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }

[Leetcode] Unique Paths II

Follow up for "Unique Paths":

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,

There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

The total number of unique paths is 2.

Note: m and n will be at most 100.

Easy DP problem, pay attention to the initial state, I make a mistake on that the first time writing the code.

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if(m == 0) return 0;
        int n = obstacleGrid[0].length;
        if(n == 0) return 0;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            if(obstacleGrid[0][i] == 1)
                dp[i] = 0;
            else 
                dp[i] = (i == 0 ? 1 : dp[i-1]);
        }
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else
                    dp[j] = dp[j] + (j == 0 ? 0 : dp[j-1]);
            }
        }
        return dp[n-1];
    }

[Leetcode] Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

DP problem. Use the same idea as in here. However, since we need to find all possible ways to split the string, the break statement should be removed. What's more, we need to reconstruct how to split the string, we need to store this information, so we use match[i][j] to indicate whether s[i...j] is a word in dict. Then use a recurse method to reconstruct all possible split.

public class Solution {
    
 public List<String> wordBreak(String s, Set<String> dict) {
  int n = s.length();
  boolean[] dp = new boolean[n];
  boolean[][] match = new boolean[n][n];
  
  for(int i = 0; i < n; i++) {
      dp[i] = false;
      for(int j = 0; j <= i; j++) {
          if(j == 0) {
              if(dict.contains(s.substring(0, i+1)) == true) {
                  dp[i] = true;
                  match[0][i] = true;
              }
          }
          else {
                  if(dp[j-1] == true && dict.contains(s.substring(j, i+1)) == true) {
                      dp[i] = true;
                      match[j][i] = true;
                  }
          }
      }
  }
  List<String> result = new ArrayList<String>();
  if(dp[n-1] == false)
      return result;
  dfs(match, s, "", 0, n, result);
  return result;
 }
 
 private void dfs(boolean[][] match, String s, String current, int beg, int n, List<String> result) {
     if(beg == n)
         result.add(current);
     else {
         for(int i = beg; i < n; i++) {
             if(match[beg][i] == true) {
                 StringBuffer sb = new StringBuffer(current);
                 sb.append(s.substring(beg, i+1));
                 if(i != n-1)
                     sb.append(" ");
                 dfs(match, s, sb.toString(), i+1, n, result);
             }
         }
     }
 }
}

[Leetcode] Word Break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

DP problem. We use dp[i] to indicate wether s[0...i] could be split by the dict or not. Then only when we find some position j that dp[j-1] == true and s[j...i] is contained in the dict, dp[i] = true. Be careful when j = 0.

    public boolean wordBreak(String s, Set dict) {
        int n = s.length();
        boolean[] dp = new boolean[n];
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0) {
                    if(dict.contains(s.substring(0, i+1)) == true) {
                        dp[i] = true;
                        break;
                    }
                }
                else {
                    if(dp[j-1] == true && dict.contains(s.substring(j, i+1)) == true) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        
        return dp[n-1];
    }

[Leetcode] Distinct Subsequences

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.

DP problem. We use dp[i][j] to indicate the number of T[0...j] in S[0...i]. Then we could have following statements:

1. if S[i] == T[j], we could match T[j] to S[i] to get some new staffs and plus the prior ones thus we have dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
2. if S[i] != T[j], we could only thous prior ones which give dp[i][j] = dp[i-1][j].

Pay attention to the initial states.

    public int numDistinct(String S, String T) {
        int m = S.length();
        int n = T.length();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= m; i++) {
            for(int j = 0; j <= n; j++) {
                if(i == 0 && j == 0)
                    dp[i][j] = 1;
                else if(i == 0)
                    dp[i][j] = 0;
                else if(j == 0) 
                    dp[i][j] = dp[i-1][j];
                else {
                    if(S.charAt(i-1) == T.charAt(j-1))
                        dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
        }
        
        return dp[m][n];
    }

[Leetcode] Decode Ways

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.

DP problem, use dp[i] to indicate the number of ways to decode the string ended at i:

1. if s[i] == 0, only when i > 0 and s[i-1] = 1 or s[i-1] = 2 do we have the way to decode, so in this case, dp[i] = dp[i-2] if i > 1 or dp[i] = 1; otherwise, we could not decode the string
2. when s[i] != 0, we at least have one way to decode, thus, dp[i] = dp[i-1] if i > 0 or dp[i] = 1 if i = 0. Then we try to see if we could use this digit with its prior one to decode one character, that is, the s[i-1... i] is a number between 10 and 26 inclusively, in this case we add the prior's way, which is dp[i-2].

    public int numDecodings(String s) {
        int n = s.length();
        if(n == 0)
            return 0;
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            if(s.charAt(i) == '0') {
                if(i > 0 && (s.charAt(i-1) == '1' || s.charAt(i-1) == '2'))
                    dp[i] = (i > 1 ? dp[i-2] : 1);
                else
                    return 0;
            }
            else {
                dp[i] = (i > 0 ? dp[i-1] : 1);
                if(i > 0) {
                    int num = Integer.parseInt(s.substring(i-1, i+1));
                    if(num >= 10 && num <= 26) 
                        dp[i] += (i > 1 ? dp[i-2] : 1);
                }
            }
        }
        return dp[n-1];
    }

[Leetcode] Edit Distance

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

一道经典的DP题目，我们用dp[i][j]表示将word1长度0...i-1和word2长度0...j-1变成相同字符串的所需的最少操作次数。那么有以下几种情况:

1. word1[i-1] == word2[j-1]，那么dp[i][j] = dp[i-1][j-1]
2. 否则，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1.其中，dp[i-1][j-1]代表替换操作，dp[i-1][j]代表插入操作，dp[i][j-1]代表删除操作

    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m+1][n+1];
        
        for(int i = 0; i <= n; i++)
            dp[0][i] = i;
        for(int i = 0; i <= m; i++)
            dp[i][0] = i;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <=n ;j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1))
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
            }
        }
        
        return dp[m][n];
    }

[Leetcode] Interleaving String

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.

DP题目，定义状态dp[i][j]表示s1长度为i的子串和s2长度为j的子串能否构成s3长度为i+j的子串，这三个子串都是从头开始的。如果dp[i-1][j]为true而且s1的i和s3的i+j相等，或者dp[i][j-1]为true而且s2的j和s3的i+j相等，那么说明dp[i][j]为true。实际实现的时候注意一下下标的问题，矩阵中的坐标比实际的要大1。

    public boolean isInterleave(String s1, String s2, String s3) {
        int n = s1.length();
        int m = s2.length();
        if(m+n != s3.length())
            return false;
        boolean[][] dp = new boolean[n+1][m+1];
        
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                if(i == 0 && j == 0) 
                    dp[i][j] = true;
                else if(i == 0) {
                    if(dp[i][j-1] == true && s2.charAt(j-1) == s3.charAt(i+j-1))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                else if(j == 0) {
                    if(dp[i-1][j] == true && s1.charAt(i-1) == s3.charAt(i+j-1))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                else {
                    if((dp[i-1][j] == true && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] == true && s2.charAt(j-1) == s3.charAt(i+j-1)))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
            }
        }
        
        return dp[n][m];
    }

[Algorithm] Find the Number of Palindrome in a String

You are given a string, count the number of palindrome in it.

A very naive solution is to enumerate all possible substrings and check if they are palindrome or not. The time complexity would be O(n^3). A better way is to use each one character and two continue characters as the center of the palindrome and expand to left and right. The time complexity would be O(nk) where k is the longest radix of palindrome. The worst case would be O(n^2). If we use DP method to find all palindrome, as mentioned in my prior post, the time complexity would be O(n^2). The best way is to use Manacher algorithm to find all possible palindrome and then count the number, which would give O(n) time complexity.

import java.util.*;

public class CountTheNumberofPalindrome {
 private static String process(String s) {
  StringBuffer sb = new StringBuffer();
  sb.append('#');
  for(int i = 0; i < s.length(); i++) {
   sb.append(s.charAt(i));
   sb.append('#');
  }
  return sb.toString();
 }

 private static int[] Manacher(String s) {
  String ns = process(s);
  int[] P = new int[ns.length()];
  int C = 0, R = 0;
  for(int i = 0; i < ns.length(); i++) {
   int mirror = 2*C - i;
   P[i] = R > i ? Math.min(R-i, P[mirror]) : 0;

   while(i+P[i]+1 < ns.length() && i-P[i]-1 >= 0 && ns.charAt(i+P[i]+1) == ns.charAt(i-P[i]-1))
    P[i]++;

   if(i+P[i] > R) {
    C = i;
    R = i + P[i];
   }
  }
  return P;
 }

 public static int count(String s) {
  int[] P = Manacher(s);
  int cnt = 0;
  for(int i = 0; i < P.length; i++) {
   cnt  = cnt + (P[i] + 1) / 2;
  }
  return cnt;
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   System.out.println(count(scan.next()));
  }
 }
}

[Leetcode] Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
逐层遍历，计算一个height数组表示目前的高度值然后在这个数组上计算最大矩形的面积。计算的时候利用DP的方法来寻找某一点向左和向右所能达到的最远距离，也就是从这个最远距离到我们这个点可以形成一个递减的序列，比如说我们已经要计算i所能到达的最左距离，我们先比较i-1和i高度的大小，如果i-1不低于i，那么i-1最左能到达的地方i也能到达，设这个地方为k，那么我们继续比较k-1和i的高度，如此继续直到条件不能再满足。这一点上的面积就是(R - L + 1)*height。时间复杂度为O(n)。整体的复杂度为O(mn)。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length;
        if(m == 0) return 0;
        int n = matrix[0].length;
        if(n == 0) return 0;
        int[] height = new int[n];
        for(int i = 0; i < n; i++)
            height[i] = 0;
        int result = Integer.MIN_VALUE;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] == '1')
                    height[j]++;
                else
                    height[j] = 0;
            }
            result = Math.max(result, Rectangle(height));
        }
        return result;
    }
    
    private int Rectangle(int[] height) {
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = 0;
        for(int i = 1; i < n; i++) {
            int ind = i;
            while(ind > 0 && height[ind-1] >= height[i])
                ind = left[ind-1];
            left[i] = ind;
        }
        right[n-1] = n-1;
        for(int i = n-2; i >= 0; i--) {
            int ind = i;
            while(ind < n-1 && height[ind+1] >= height[i])
                ind = right[ind+1];
            right[i] = ind;
        }
        int ma = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            ma = Math.max(ma, height[i]*(right[i] - left[i] + 1));
        }
        return ma;
    }
}

[Leetcode] Palindrome Partitioning II

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

首先找出所有可能的回文情况，使用DP的方法的话时间复杂度为O(n^2)，情况如下：

1. i == j, dp[i][j] = true, 单个字符自己肯定是回文字符串
2. i+1 == j, dp[i][j] = true, 两个字符的时候相等的话就是回文字符串
3. 其他情况，当i和j的字符相同而且dp[i+1][j-1]为回文的话，那么dp[i][j]也是回文

在寻找最小的cut的时候，也是O(N^2)级别的DP，dp[j] = argmin dp[t] + 1且 t+1到j为回文，注意处理一下t为0的特殊情况就可以了。

    public int minCut(String s) {
        if(s == null) return 0;
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(i == j)
                    dp[i][j] = true;
                else if(i+1 == j) {
                    if(s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                    else 
                        dp[i][j] = false;
                }
                else {
                    if(dp[i+1][j-1] == true && s.charAt(i) == s.charAt(j))
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
            }
        }
        int[] cut = new int[n];
        for(int i = 0; i < n; i++) {
            cut[i] = Integer.MAX_VALUE;
            for(int j = 0; j <= i; j++) {
                if(j == 0 && dp[j][i] == true)
                    cut[i] = 0;
                else if(dp[j][i] == true)
                    cut[i] = Math.min(cut[j-1]+1, cut[i]);
            }
        }
        return cut[n-1];
    }

[Leetcode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

比较简单的DP题目，我们全程保持最优解以及以当前元素结尾的连续子数组的最大和。

    public int maxSubArray(int[] A) {
        int n = A.length;
        int max = A[0], result = A[0];
        for(int i = 1; i < n; i++) {
            max = Math.max(A[i] + max, A[i]);
            result = Math.max(max, result);
        }
        return result;
    }

这道题还有一种变种，这里是只寻找一个连续的子数组，变种是让你寻找m个连续的子数组，求解使得其和最大，这个问题的解法我稍后再补上。

[Leetcode] Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

比较简单的DP题目，状态转移方程为f(i, j) = f(i-1, j-1) + f(i-1, j) + c(i, j). 最直接的方法是是用二维数组去存计算的结果，但是我们发现每一次的dp只用到了上一次的dp结果，因此实际使用一个一维数组就足够了，注意更新的时候从后面往前更新，因为我们需要用到之前的结果。

    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        dp[0] = triangle.get(0).get(0);
        for(int i = 1; i < n; i++) {
            for(int j = i; j >= 0; j--) {
                if(j == i)
                    dp[j] = dp[j-1] + triangle.get(i).get(j);
                else if(j == 0) 
                    dp[j] = dp[j] + triangle.get(i).get(j);
                else
                    dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++) 
            min = min > dp[i] ? dp[i] : min;
        return min;
    }

[Leetcode] Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

数据结构题，使用栈来进行判断，要注意检查栈空的情况。

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            }
            else {
                if(stack.size() == 0) return false;
                if(s.charAt(i) == ')' && stack.pop() != '(') 
                    return false;
                if(s.charAt(i) == ']' && stack.pop() != '[')
                    return false;
                if(s.charAt(i) == '}' && stack.pop() != '{')
                    return false;
            }
        }
        if(stack.size() == 0)
            return true;
        else
            return false;
    }

今天在论坛上看到了一个变种，除了括号以外，还加入了一个元素X，能够匹配任意的括号，求问一个给定的输入是否是一个合法的括号匹配。这道题可以使用O(n^3)的dp来做，对于每一个dp[i][j], 当存在k使得 dp[i][k] == true 且 dp[k+1][j] == true的时候，那么dp[i][j] = true，然而还有一种匹配的形式就是nested形式的匹配，上面的是并列，nested就是套起来的那种，所以需要检查i, j与dp[i+1][j-1]。总而言之，这道题可以看做是word break和palindrome的综合。下面是我写的代码，测试了几组样例：

1. [X]X ----> TRUE
2. []{}[X]X -----> TRUE
3. [X]] -------> TRUE
4. []X)([} -------> FALSE
5. [ ------> FALSE
6. }{ -------> FALSE
7. X}{X ------->TRUE

希望大家提供更多的样例来验证程序的对错。

import java.util.*;

public class ValidParenteses {
 public static boolean isValid(String s) {
  int n = s.length();
  boolean[][] dp = new boolean[n][n];

  for(int i = n-1; i >= 0; i--) {
   for(int j = i; j < n; j++) {
    if(i == j) {
     dp[i][j] = false; // single character could not be valid
    }
    else if(j == i+1) {
     if(s.charAt(i) == 'X' || s.charAt(j) == 'X') 
      dp[i][j] = true;
     else {
      if(s.charAt(i) == '(' && s.charAt(j) == ')')
       dp[i][j] = true;
      else if(s.charAt(i) == '[' && s.charAt(j) == ']')
       dp[i][j] = true;
      else if(s.charAt(i) == '{' && s.charAt(j) == '}')
       dp[i][j] = true;
      else
       dp[i][j] = false;
     }
    }
    else {
     if(dp[i+1][j-1] == false)
      dp[i][j] = false;
     else {
      if(s.charAt(i) == 'X' || s.charAt(j) == 'X') 
       dp[i][j] = true;
      else {
       if(s.charAt(i) == '(' && s.charAt(j) == ')')
        dp[i][j] = true;
       else if(s.charAt(i) == '[' && s.charAt(j) == ']')
        dp[i][j] = true;
       else if(s.charAt(i) == '{' && s.charAt(j) == '}')
        dp[i][j] = true;
       else
        dp[i][j] = false;
      }
     }
     for(int k = i+1; k <= j-2; k++) {
      if(dp[i][k] == true && dp[k+1][j] == true) {
       dp[i][j] = true;
       break;
      }
     }
    }
   }
  }
  return dp[0][n-1];
 }

 public static void main(String[] args) {
  Scanner scan = new Scanner(System.in);
  while(scan.hasNext()) {
   System.out.println(isValid(scan.next()));
  }
 }
}

[Leetcode] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

比较naive的方法是扫描两遍，第一遍记录0，1，2的个数，然后第二遍扫描的时候按照个数来存值。另外一种方法是使用一种叫做三路归并的技术，这种技术在快速排序中经常用到，以此来提高快排在数组中存在大量重复元素的时候的效率。

    public void sortColors(int[] A) {
        int start = 0, current = 0, back = A.length - 1;
        // start position of 1s if exist, current position, the first element before continue 2s
        while(current <= back) {
            if(A[current] == 1)
                current++;
            else if(A[current] == 0) {
                A[current] = A[start]; // current and start might be the same
                A[start] = 0;
                start++; current++;
            }
            else {
                A[current] = A[back];
                A[back] = 2;
                back--;
            }
        }
    }

[Leetcode] First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

使用桶排序的思想，用A[i]去装i+1，拍好序之后寻找第一个和自己标号不对应的“桶”的位置。

    public int firstMissingPositive(int[] A) {
        for(int i = 0; i < A.length; i++) {
            int num = A[i], temp;
            while(num > 0 && num <= A.length && A[num-1] != num) {
                temp = A[num-1];
                A[num-1] = num;
                num = temp;
            }
        }
        for(int i = 0; i < A.length; i++) {
            if(A[i]-1 != i)
                return i+1;
        }
        return A.length + 1 ;
    }

[Leetcode] Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and nrespectively.

指针题，其实就是在考察inplace的操作。

    public void merge(int A[], int m, int B[], int n) {
        int endA = m - 1;
        int endB = n - 1;
        int end = m + n - 1;
        while(endA >= 0 && endB >= 0) {
            if(A[endA] > B[endB])
                A[end--] = A[endA--];
            else 
                A[end--] = B[endB--];
        }
        while(endB >= 0)
            A[end--] = B[endB--];
    }

[Leetcode] Populating Next Right Pointers in Each Node

Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

使用和Populating Next Right Pointers in Each Node II一样的方法就可以了，也可以使用递归的方法，在两个节点上递归，先把同一个节点上的左右节点连接在一起，然后在把左边的右子树和右边的左子树连接在一起。

    public void connect(TreeLinkNode root) {
        while(root != null) {
            TreeLinkNode next = null, pre = null;
            for(; root != null; root = root.next) {
                if(next == null) next = root.left == null ? root.right : root.left;
                if(root.left != null) {
                    if(pre != null) pre.next = root.left;
                    pre = root.left;
                }
                if(root.right != null) {
                    if(pre != null) pre.next = root.right;
                    pre = root.right;
                }
            }
            root = next;
        }
    }

[Leetcode] Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

判断一棵树是否是二叉搜索树，根据定义，根比左子树所有的节点都大，比右子树所有的节点都小。我们可以利用二叉搜索树的性质：中序遍历为严格递增来判断一颗树是否合法。使用Morris遍历同时保持上一个遍历的节点，可以达到时间复杂度O(n)空间复杂度O(1)的方法。

    public boolean isValidBST(TreeNode root) {
        TreeNode pre = null, cur = root, tmp;
        while(cur != null) {
            if(cur.left == null) {
                if(pre != null && pre.val >= cur.val) 
                    return false;
                pre = cur;
                cur = cur.right;
            }
            else {
                tmp = cur.left;
                while(tmp.right != null && tmp.right != cur)
                    tmp = tmp.right;
                if(tmp.right == null) {
                    tmp.right = cur;
                    cur = cur.left;
                }
                else {
                    tmp.right = null;
                    if(pre != null && pre.val >= cur.val) 
                        return false;
                    pre = cur;
                    cur = cur.right;
                }
            }
        }
        return true;
    }

另一方面，我们也可以使用递归求解，但是在递归的时候不能简单的判断根与左右子树的节点的大小，而必须判断根是否在一个范围以内(min, max)，在递归调用的时候，先判断当前的根是否在范围内，然后递归的时候左子树的max变为当前根的值，右子树的min变成当前根的值，这样保证区间合法，然后判断左右子树是否合法。这种方法的时间复杂度同样是O(n)，但是空间复杂度大概为O(logn)。

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, int min, int max) {
        if(root == null)
            return true;
        if(root.val > min && root.val < max && isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max))
            return true;
        return false;
    }

[Leetcode] Populating Next Right Pointers in Each Node II

Follow up for problem "Populating Next Right Pointers in Each Node".

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

可以使用层次遍历的方法，但是空间复杂度为O(n)，为了达到O(1)，使用两个指针一个保存上一层的信息一个用来链接下一层的信息，因为上一层已经连接在一起，所以可以直接扫过去，然后我实现的思路是根据当前下一层节点与上一层节点的关系，来找到第一个合法的next，这样写比较冗长，一种比较好的思路是直接根据已经链接的节点来直接链接他们的孩子，注意在每次链接完一层，要找下一层的开始地方。

    public void connect(TreeLinkNode root) {
        if(root == null) return;
        root.next = null;
        TreeLinkNode parent = root;
        TreeLinkNode child = (root.left == null) ? (root.right) : (root.left);
        while(child != null) {
            TreeLinkNode temp1 = parent;
            TreeLinkNode temp2 = child;
            while(temp1 != null) {
                if(temp2 == temp1.left) {
                    if(temp1.right != null) {
                        temp2.next = temp1.right;
                        temp2 = temp2.next;
                    }
                    else {
                        temp1 = temp1.next;
                    }
                }
                else if(temp2 == temp1.right) {
                    temp1 = temp1.next;
                }
                else { // find next valid node with left or right child
                    while(temp1 != null && temp1.left == null && temp1.right == null) temp1 = temp1.next;
                    if(temp1 == null) temp2.next = null;
                    else if(temp1.left != null) {
                        temp2.next = temp1.left;
                        temp2 = temp2.next;
                    }
                    else {
                        temp2.next = temp1.right;
                        temp2 = temp2.next;
                    }
                }
            }
            temp1 = child; // find next level's start position
            while(temp1 != null && temp1.left == null && temp1.right == null) temp1 = temp1.next;
            if(temp1 == null) child = null;
            else {
                parent = temp1;
                child = (temp1.left == null) ? (temp1.right) : (temp1.left);
            }
        }
    }

    public void connect(TreeLinkNode root) {
        while(root != null) {
            TreeLinkNode next = null;
            TreeLinkNode pre = null;
            for(; root != null; root = root.next) {
                if(next == null) next = root.left == null ? root.right : root.left;
                if(root.left != null) {
                    if(pre != null) pre.next = root.left;
                    pre = root.left;
                }
                if(root.right != null) {
                    if(pre != null) pre.next = root.right;
                    pre = root.right;
                }
            }
            root = next;
        }
    }

[Leetcode] Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
如果使用O(n)的空间来做的话比较简单，用一个链表来存储树的中序遍历的结果，因为BST的中序遍历应该是一个递增的序列，那么再扫一遍这个链表找到两个错位的节点就可以了。但是如果使用O(1)的空间做，那么就需要搬出Morris遍历了，在遍历的过程中比较当前节点和前一节点的大小关系来进行判断。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode node1 = null, node2 = null, pre = null;
        TreeNode cur = root, tmp;
        while(cur != null) {
            if(cur.left == null) {
                if(pre != null) {
                    if(cur.val < pre.val) {
                        if(node1 == null) 
                            node1 = pre;
                        node2 = cur;
                    }
                }
                pre = cur;
                cur = cur.right;
            }
            else {
                tmp = cur.left;
                while(tmp.right != null && tmp.right != cur) tmp = tmp.right;
                if(tmp.right == null) {
                    tmp.right = cur;
                    cur = cur.left;
                }
                else {
                    if(pre != null) {
                        if(cur.val < pre.val) {
                            if(node1 == null) 
                                node1 = pre;
                            node2 = cur;
                        }
                    }
                    pre = cur;
                    tmp.right = null;
                    cur = cur.right;
                }
            }
        }
        int n = node1.val;
        node1.val = node2.val;
        node2.val = n;
    }
}

[Leetcode] Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

比较Tricky的思路，按照普通的层次遍历之后，每隔一层就将结果翻转一次。但是一个问题是，这样的输出的确符合问题的要求，但是过程并不符合，这能算是正确的解法么？就比如对于一颗BST，题目要求你中序输出，但是其实你先序输出之后再排序一样能得到结果的。如果严格按照题目的要求，可以用一个变量来记录现在是从左往右还是从右往左。从左往右的话先加左子树再右子树，从右往左的话先右子树再左子树还需要再reverse一下。

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> level1 = new ArrayList<TreeNode>();
        List<TreeNode> level2;
        if(root == null) return result;
        level1.add(root);
        while(level1.size() != 0) {
            level2 = new ArrayList<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            for(TreeNode node : level1) {
                list.add(node.val);
                if(node.left != null) level2.add(node.left);
                if(node.right != null) level2.add(node.right);
            }
            result.add(list);
            level1 = level2;
        }
        for(int i = 1; i < result.size(); i+=2) {
            Collections.reverse(result.get(i));
        }
        return result;
    }

[Leetcode] Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

从下往上的层次遍历，两种方法，递归或者使用stack，或者直接使用Collections.reverse()方法来把原来的结果翻转，原理和本质是一样的。

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> level1 = new ArrayList<TreeNode>();
        List<TreeNode> level2;
        if(root == null) return result;
        level1.add(root);
        while(level1.size() != 0) {
            level2 = new ArrayList<TreeNode>();
            List<Integer> list = new ArrayList<Integer>();
            for(TreeNode node : level1) {
                list.add(node.val);
                if(node.left != null) level2.add(node.left);
                if(node.right != null) level2.add(node.right);
            }
            result.add(list);
            level1 = level2;
        }
        Collections.reverse(result);
        return result;
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(root == null) return result;
        List<TreeNode> roots = new ArrayList<TreeNode>();
        roots.add(root);
        recurse(roots, result);
        return result;
    }
    
    private void recurse(List<TreeNode> roots, List<List<Integer>> result) {
        if(roots.size() == 0) return ; // terminate condition
        List<TreeNode> children = new ArrayList<TreeNode>();
        List<Integer> list = new ArrayList<Integer>();
        for(TreeNode node : roots) {
            list.add(node.val);
            if(node.left != null) children.add(node.left);
            if(node.right != null) children.add(node.right);
        }
        recurse(children, result);
        result.add(list);
    }