[LeetCode] Subsets II

Thought: easy DFS.

Code:
public class Solution {
    public static ArrayList<ArrayList<Integer>> result;
    public ArrayList<Integer> cache;
    public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        result = new ArrayList<ArrayList<Integer>>();
        cache = new ArrayList<Integer>();
        dfs(num, 0, num.length);
        return new ArrayList<ArrayList<Integer>>(new HashSet<ArrayList<Integer>>(result));
    }
    public void dfs(int[] num, int current, int length) {
        if (current == length) {
            result.add(new ArrayList<Integer>(cache));
            return;
        }
        dfs(num, current + 1, length);
        cache.add(num[current]);
        dfs(num, current + 1, length);
        cache.remove(cache.size() - 1);
    }
}

[LeetCode] Restore IP Addresses

Thought: Easy to think of dfs. Then try to code it.

Code:
public class Solution {
    public static ArrayList<String> result;
    public static StringBuilder cache;
    public ArrayList<String> restoreIpAddresses(String s) {
        result = new ArrayList<String>();
        cache = new StringBuilder();
        if (s.length() <= 3) return result;
        dfs(s, 0, 4, 0);
        return result;
    }
    public boolean isValid(String s) {
        if (s.length() == 1) return true;
        else if (s.length() == 2) {
            return s.charAt(0) != '0';
        }else if (s.length() == 3) {
            if (s.charAt(0) == '0') return false;
            if (s.charAt(0) == '1') return true;
            if (s.charAt(0) >= '3') return false;
            else {
                if (s.charAt(1) <= '4') return true;
                if (s.charAt(1) >= '6') return false;
                else {
                    return s.charAt(2) <= '5';
                }
            }
        }else {
            return false;
        } 
    }
    public void dfs(String s, int segment, int target, int current) {
        if (segment == target) {
            if (current == s.length()) {
                cache.delete(cache.length() - 1, cache.length());
                result.add(cache.toString());
                cache.append('.');
                return;
            }else {
                return;
            }
        }
        if (current < s.length() && isValid(s.substring(current, current + 1))) {
            cache.append(s.substring(current, current + 1));
            cache.append('.');
            dfs(s, segment + 1, target, current + 1);
            cache.delete(cache.length() - 2, cache.length());
        }
        if ((current < s.length() - 1) && isValid(s.substring(current, current + 2)))  {
            cache.append(s.substring(current, current + 2));
            cache.append('.');
            dfs(s, segment + 1, target, current + 2);
            cache.delete(cache.length() - 3, cache.length());
        }
        if ((current < s.length() - 2) && isValid(s.substring(current, current + 3))){
            cache.append(s.substring(current, current + 3));
            cache.append('.');
            dfs(s, segment + 1, target, current + 3);
            cache.delete(cache.length() - 4, cache.length());
        }
    }
}

[LeetCode] Triangle

Thought: DP. Use the Array to ensure O(n) space.

Code:
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int[] result = new int[triangle.size()];
        for (int i = 0; i < triangle.size(); i++) {
            result[i] = triangle.get(triangle.size() - 1).get(i);
        }
        for (int i = 1; i < triangle.size(); i++) {
            for (int j = 0; j < triangle.size() - i; j++) {
                result[j] = Math.min(result[j], result[j + 1]) + triangle.get(triangle.size() - i - 1).get(j);
            }
        }
        return result[0];
    }
}

[LeetCode] Palindrome Partitioning II

Thought: DP. f(i) = 1 + min(f(j)) where palindrome(i, j) = true.

Code:
public class Solution {
    public int minCut(String s) {
        if (s.length() == 0) return 0;
        boolean[][] palindrome = new boolean[s.length()][s.length()];
        for (int j = s.length() - 1; j >= 0; j--) {
            for (int i =  0; i <= j; i++) {
                palindrome[j][i] = true;
            }
        }
        for (int j = s.length() - 2; j >= 0; j--) {
            for (int i = j + 1; i < s.length(); i++) {
                palindrome[j][i] = palindrome[j + 1][i - 1] && (s.charAt(j) == s.charAt(i));
            }
        }
        int[] result = new int[s.length() + 1];
        result[0] = -1;
        for (int i = 2; i <= s.length(); i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                if (palindrome[j - 1][i - 1]) {
                    min = Math.min(min, result[j - 1]);
                }
            }
            result[i] = 1 + min;
        }
        return result[s.length()];
    }
}

[LeetCode] Recover Binary Search Tree

Thought: Recursion way is trivial.

Code:

public class Solution {

    public static TreeNode previous, first, second;

    public void recoverTree(TreeNode root) {

        previous = null;

        first = null;

        second = null;

        inorder(root);   

        swap(first, second);

    }

    public void inorder(TreeNode root) {

        if (root == null) return;

        if (root.left != null) inorder(root.left);

        dosomething(root);

        if (root.right != null) inorder(root.right);

    }

    public void dosomething(TreeNode root) {

        if (previous != null && root.val < previous.val) {

            if (first == null) {

                first = previous;

                second = root;

            }else second = root;

        }

        previous = root;

    }

    public void swap(TreeNode first, TreeNode second) {

        int temp = first.val;

        first.val = second.val;

        second.val = temp;

    }

}

Note: There exists a smart traversal method -> Inorder Morris Traversal 
No Recursion, no stack!!!
   
 public void inorder(TreeNode root) {
        if (root == null) return;
        TreeNode cur = root;
        while (cur != null) { 
            if (cur.left == null) { // no left child -> visit and step right
                dosomething(cur);
                cur = cur.right;
            }else {
                TreeNode tmp = cur.left; 
                while (tmp.right != null && tmp.right != cur) { // let tmp step rightest
                    tmp = tmp.right;
                }
                if (tmp.right == null) { // tmp is leaf -> build circle and step left
                    tmp.right = cur;
                    cur = cur.left;
                }else {
                    tmp.right = null; // tmp is already in circle -> destroy circle, visit, and step right
                    dosomething(cur);
                    cur = cur.right;
                }
            }
        }

    }

[LeetCode] Word Search

Thought:
It is a DFS problem.

Code:
public class Solution {
    public static boolean flag;
    public boolean exist(char[][] board, String word) {
        flag = false;
        int row = board.length;
        int column = board[0].length;
        boolean[][] visited = new boolean[row][column];
        
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                helper(board, i, j, word, visited);
            }
        }
        
        return flag;        
    }
    public void helper(char[][] board, int row, int column, String word, boolean[][] visited) {
        if (flag) return;
        if (word.length() == 0) {
            flag = true;
            return;        
        }
        if (row >= board.length || column >= board[0].length || row < 0 || column < 0) return;
        if (visited[row][column] || board[row][column] != word.charAt(0)) return;
        visited[row][column] = true;
        helper(board, row - 1, column, word.substring(1), visited);
        helper(board, row, column - 1, word.substring(1), visited);
        helper(board, row + 1, column, word.substring(1), visited);
        helper(board, row, column + 1, word.substring(1), visited); 
        visited[row][column] = false;
    }
}

[LeetCode] Search for a Range

Thought:
Find the largest index whose value is not more than target.

Code:
public class Solution {
    public int[] searchRange(int[] A, int target) {
       
        int[] ret = new int[2];
        ret[0] = helper(A, target - 1);
        ret[1] = helper(A, target);
        if (ret[1] != -1 && A[ret[1]] == target) ret[0]++;
        if (ret[0] != -1 && A[ret[1]] != target) ret[0] = ret[1] = -1;

        return ret;
    }   
    public int helper (int[] a, int x) {
        int start = 0;
        int end = a.length - 1;
        int mid = (start + end)/2;
        int result = -1;

        while (start <= end) {
            if (a[mid] > x) {
                end = mid - 1;
                mid = (start + end)/2;
            }else {
                start = mid + 1;
                result = mid;
                mid = (start + end)/2;
            }
        }
        return result;
    }
}

[LeetCode] Search in Rotated Sorted Array

Thought:
Binary Search with different condition.

Code:
public class Solution {
    public int search(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) return mid;
            if (A[start] > A[mid]) {
                if (A[mid] <= target && target <= A[end]) start = mid + 1;
                else end = mid - 1;
            }else {
                if (A[start] <= target && target <= A[mid]) end = mid - 1;
                else start = mid + 1;
            }
        }
        return - 1;
    }
}

[LeetCode] Search in Rotated Sorted Array II

Thought:
Update the condition. This will change the Time to O(n).

Code:
public class Solution {
    public boolean search(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (A[mid] == target) return true;
            if (A[start] > A[mid]) {
                if (A[mid] <= target && target <= A[end]) start = mid + 1;
                else end = mid - 1;
            }else if (A[start] < A[mid]){
                if (A[start] <= target && target <= A[mid]) end = mid - 1;
                else start = mid + 1;
            }else {
                start++;
            }
        }
        return false;
    }
}

[LeetCode] Sqrt(x)

Thought:
It is a Binary Search.

Code:
public class Solution {
    public int sqrt(int x) {
        if (x == 0) return 0;       
        int result = 2;
        int tmp = 1;
       
        while ( !(result <= x/result && result + 1 > x/(result + 1)) ) {
            if (result < x/result) {
                tmp = result;
                result = result * result;
            }else {
                result = (result + tmp) / 2;
            }
        }
        return result;
    }
}

[LeetCode] Word Ladder

Thought:
It is a BFS problem.

Code:
import java.util.*;
public class Solution {
    public int ladderLength(String start, String end, HashSet<String> dict) {
        LinkedList<String> q1 = new LinkedList<String>(); // as a queue
        LinkedList<Integer> q2 = new LinkedList<Integer>(); // as a queue
        q1.offer(start);
        q2.offer(1);
        dict.remove(start);
        while (!q1.isEmpty()) {
            String current = q1.poll();
            int depth = q2.poll();
            if (current.equals(end)) return depth;
            Iterator<String> it = dict.iterator();
            while(it.hasNext()) {
                String tmp = it.next();
                if (adjacent(tmp, current)) {
                    q1.offer(tmp);
                    q2.offer(depth + 1);    
                    it.remove();
                }                
            }
        }
        return 0;
    }
    public boolean adjacent(String a, String b) {
        int result = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) result++;
        }
        return result == 1;
    }
}

[LeetCode] Valid Number

Thought: 
There is a very clear solution using state machines.

Code:
public class Solution {
    public boolean isNumber(String s) {
        char[] tmp = s.toCharArray();
        int[][] trans = {
            { 0 ,0 ,0 ,0 ,0 ,0 },// false
            { 0 ,2 ,3 ,0 ,1 ,4 },// 1
            { 0 ,2 ,5 ,6 ,9 ,0 },// 2
            { 0 ,5 ,0 ,0 ,0 ,0 },// 3
            { 0 ,2 ,3 ,0 ,0 ,0 },// 4
            { 0 ,5 ,0 ,6 ,9 ,0 },// 5
            { 0 ,7 ,0 ,0 ,0 ,8 },// 6
            { 0 ,7 ,0 ,0 ,9 ,0 },// 7
            { 0 ,7 ,0 ,0 ,0 ,0 },// 8
            { 0 ,0 ,0 ,0 ,9 ,0 } // 9
        };
        int i = 0;
        int stat = 1;
        while (i < tmp.length) {
            int type = 0;
            if (tmp[i] >= '0' && tmp[i] <= '9') type = 1;
            else if (tmp[i] == '.') type = 2;
            else if (tmp[i] == 'e') type = 3;
            else if (tmp[i] == ' ') type = 4;
            else if (tmp[i] == '+' || tmp[i] == '-') type = 5;
            stat = trans[stat][type];
            i++;
        }
        return stat == 2 || stat == 5 || stat == 7 || stat == 9;
    }
}

Note:

	type	0	1	2	3	4	5
stat		others	digits	point	e	space	sign
0	FALSE
1	only space
2	digits
3	only point
4	sign
5	digits.
6	e
7	e digits
8	e sign
9	valid space

[LeetCode] Partition List

Thought:
Find the first value that is equal or larger than x. Then put every smaller one before it.

Code:
public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
     
        ListNode small = sentinel;
        ListNode large = head;
     
        while (large != null) {
            if (large.val >= x) break;
            small = small.next;
            large = large.next;
        }
     
        if (large == null) return sentinel.next;
     
        while (large.next != null) {
            ListNode tmp = large.next;
            if (tmp.val < x) {
                large.next = tmp.next;
                tmp.next = small.next;
                small.next = tmp;
                small = small.next;
            }else {
                large = large.next;          
            }

        }
     
        return sentinel.next;
    }
}

[LeetCode] Palindrome Partitioning

Thought:
Classical BFS.
The format of BFS is just like this.
The end condition + the forward method.

Code:
public class Solution {
    private static ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
    private static ArrayList<String> cache = new ArrayList<String>();
   
    private boolean isPalindrome(String s, int start, int end) {
        int i = start;
        int j = end;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }
    public ArrayList<ArrayList<String>> partition(String s) {
        result.clear();
        cache.clear();
        dfs(s, 0);
        return result;
    }
    public void dfs(String s, int depth) {
        if (depth == s.length()) result.add(new ArrayList<String>(cache));
        for (int end = depth; end < s.length(); end++) {
            if (isPalindrome(s, depth, end)) {
                cache.add(s.substring(depth, end + 1));
                dfs(s, end + 1);
                cache.remove(cache.size() - 1);
            }
        }
    }   
}

[LeetCode] Validate Binary Serach Tree

Thought:
Check whether the root is in specific range.

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

[LeetCode] Set Matrix Zeros

Thought:
Constant space means we use the matrix itself to store the setting zero flag.

Code:
public class Solution {
    public void setZeroes(int[][] matrix) {
        
        int row = -1, col = -1, m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    row = i;
                    col = j;
                    i = m;
                    j = n;
                }
            }
        }

        if (row == -1 && col == -1) return;
       
        for (int i = row; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][col] = 0;
                    matrix[row][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((matrix[row][j] == 0 && j != col) || (matrix[i][col] == 0 && i != row)) matrix[i][j] = 0;
            }
        }

        for (int i = 0; i < m; i++) matrix[i][col] = 0;
        for (int j = 0; j < n; j++) matrix[row][j] = 0;

    }
}

[LeetCode] Merge Intervals

Thought:
First sort by the start time, then merge.

Code:
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

        if (intervals.size() == 0) return intervals;
        Collections.sort(intervals, BYSTART);
        ArrayList<Interval> ret = new ArrayList<Interval>();

        int s = intervals.get(0).start;
        int e = intervals.get(0).end;
        for ( Interval itv : intervals) {
            if (e >= itv.start) e = Math.max(e, itv.end);
            else {
                ret.add(new Interval(s, e));
                s = itv.start;
                e = itv.end;
            }
        }
        ret.add(new Interval(s, e));

        return ret;
    }

    private static final Comparator<Interval> BYSTART = new Comparator<Interval>(){
        public int compare (Interval i, Interval j) {
            return new Integer(i.start).compareTo(new Integer(j.start));
        }
    };
}

[LeetCode] Pow(x,n)

Thought:
Divide and Conquer.

Code:
public class Solution {
    public double pow(double x, int n) {
        boolean isNeg = false;
        if (n < 0) {
            n = - n;
            isNeg = true;
        }
        return isNeg ? 1 / helper(x, n): helper(x, n);       
    }
    public double helper(double x, int n) {      
       
        if (n == 0) return 1;       
        double result = pow(x, n / 2);
       
        if (n % 2 == 0) return result * result;
        return result * result * x;
    }
   
}

[LeetCode] Unique Binary Search Trees II

Thought:
Recursion.

Code:
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        return generateBST(1,n);
    }
    public ArrayList<TreeNode> generateBST(int start, int end){
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if(start>end){
            result.add(null);
        }else if(start==end){
            result.add(new TreeNode(start));
        }else{
            for(int i=start;i<=end;i++){                
                ArrayList<TreeNode> left = generateBST(start,i-1); 
                ArrayList<TreeNode> right = generateBST(i+1,end);
                for(int k = 0;k<left.size();k++){
                    for(int j = 0;j<right.size();j++){ 
                        TreeNode root = new TreeNode(i);
                        root.left = left.get(k);
                        root.right = right.get(j);
                        result.add(root);
                    }
                }
            }
        }        
        return result; 
    }
}

[LeetCode] Unique Binary Search Trees

Thought:
Recursion. We could also use DP to do faster.

Code:
public class Solution {
    public int numTrees(int n) {
        if (n < 2) return 1;
        if (n == 2) return 2;
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = result + numTrees(i) * numTrees(n - i - 1);
        }
        return result;      
    }
}