[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] Surrounded Regions

Thought: Any point that could not be reached if we started from four edges should be painted as 'X'.

Code:
public class Solution {
    public void solve(char[][] board) {
        int rows = board.length;
        if (rows == 0) return;
        int cols = board[0].length;
        for (int j = 0; j < cols; j++) markFrom(board, 0, j);
        for (int i = 0; i < rows; i++) markFrom(board, i, 0);
        for (int j = 0; j < cols; j++) markFrom(board, rows - 1, j);
        for (int i = 0; i < rows; i++) markFrom(board, i, cols - 1);
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'M') board[i][j] = 'O';
                else board[i][j] = 'X';
            }
        }    
    }
    public void markFrom(char[][] board, int x, int y) {
        int rows = board.length;
        int cols = board[0].length;
        if (x < 0 || x >= rows) return;
        if (y < 0 || y >= cols) return;
        if (board[x][y] == 'X' || board[x][y] == 'M') return;
        board[x][y] = 'M';
        markFrom(board, x - 1, y);
        markFrom(board, x, y - 1);
        markFrom(board, x + 1, y );
        markFrom(board, x, y + 1);
    }
}