Valid Sudoku: http://www.lintcode.com/en/problem/valid-sudoku/

• matrix transformation:
  • int x = j/3 + (i/3) * 3;
  • int y = j%3 + (i%3) * 3;
  • i/3 向下; i%3 向右
• first approach is lazy init

    public boolean isValidSudoku(char[][] board) {

        for (int i = 0; i < 9; i++) {
            // mark true if the digit exists
            boolean[] rows = new boolean[9];
            boolean[] cols = new boolean[9];
            boolean[] cells = new boolean[9];

            for (int j = 0; j < 9; j++) {

                // check rows
                if (board[i][j] != '.') {

                    int num = board[i][j] - '1';
                    if (rows[num]) return false;

                    rows[num] = true;
                }

                // check cols
                if (board[j][i] != '.') {

                    int num = board[j][i] - '1';
                    if (cols[num]) return false;

                    cols[num] = true;
                }

                // check cells
                int x = j/3 + (i/3) * 3;
                int y = j%3 + (i%3) * 3;
                if (board[x][y] != '.') {

                    int num = board[x][y] - '1';
                    if (cells[num]) return false;

                    cells[num] = true;
                }
            }
        }

        return true;
    }

    public boolean isValidSudoku(char[][] board) {
        // write your code here
        int index = 81;

        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] cells = new boolean[9][9];

        for (int i = 0; i < index; i++) {

            int row = i / 9;
            int col = i % 9;
            int cell = col / 3 + row / 3 * 3;

            if (board[row][col] != '.') {
                int num = board[row][col] - '1';
                if (rows[row][num] || cols[col][num] || cells[cell][num]) return false;

                rows[row][num] = true;
                cols[col][num] = true;
                cells[cell][num] = true;
            }
        }

        return true;
    }

Sudoku Solver:

• given index:
  • row = index / 9, col = index % 9, block = col / 3 + row / 3 * 3
• return true / false 来剪枝
• O(9^m), m is the blank cells
• approach 1 预处理 相比approach 2, each isValid() is expensive O(n)

class Solution {
    public void solveSudoku(char[][] board) {
        int index = 81;

        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] cells = new boolean[9][9];

        for (int i = 0; i < index; i++) {
            int row = i / 9;
            int col = i % 9;
            int cell = col / 3 + row / 3 * 3;

            if (board[row][col] != '.') {
                int num = board[row][col] - '1';
                rows[row][num] = cols[col][num] = cells[cell][num] = true;
            }
        }

        dfs(rows, cols, cells, board, 0);        
    }

    private boolean dfs(boolean[][] rows, boolean[][] cols, boolean[][] cells, char[][] board, int index) {

        if (index == 81) return true;
        int row = index / 9;
        int col = index % 9;
        int cell = col / 3 + row / 3 * 3;

        if (board[row][col] != '.') {
            return dfs(rows, cols, cells, board, index + 1);
        } else {
            for (char c = '1'; c <= '9'; c++) {
                int num = c - '1';
                if (rows[row][num] || cols[col][num] || cells[cell][num]) continue;
                board[row][col] = c;
                rows[row][num] = cols[col][num] = cells[cell][num] = true;
                if (dfs(rows, cols, cells, board, index + 1)) return true; // 找到一个解就可以
                board[row][col] = '.';
                rows[row][num] = cols[col][num] = cells[cell][num] = false;
            }            
        }
        return false;        
    }
}

public class Solution {
    public void solveSudoku(char[][] board) {
        if(board == null || board.length == 0)
            return;
        solve(board);
    }

    public boolean solve(char[][] board){
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(board[i][j] == '.'){
                    for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
                        if(isValid(board, i, j, c)){
                            board[i][j] = c; //Put c for this cell

                            if(solve(board))
                                return true; //If it's the solution return true
                            else
                                board[i][j] = '.'; //Otherwise go back
                        }
                    }

                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c){
        for(int i = 0; i < 9; i++) {
            if(board[i][col] != '.' && board[i][col] == c) return false; //check row
            if(board[row][i] != '.' && board[row][i] == c) return false; //check column
            if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' && 
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
        }
        return true;
    }
}

word ladder:

• BFS

generate parentheses

public class Solution {
    public List<String> generateParenthesis(int n) {

        List<String> rst = new ArrayList<>();        
        StringBuilder sb = new StringBuilder();

        dfs(rst, n, n, sb);

        return rst;
    }

    private void dfs(List<String> rst, int left, int right, StringBuilder sb) {

        if (left == 0 && right == 0) {
            rst.add(new String(sb));
        }

        int length = sb.length();

        if (left > 0) {
            sb.append('(');
            dfs(rst, left - 1, right, sb);
            sb.setLength(length);
        }

        if (right > left) {
            sb.append(')');
            dfs(rst, left, right - 1, sb);
            sb.setLength(length);
        }

    }
}

Restore IP Addresses

• 3^4 each level 3 possibilities, with 4 levels at max.

public class Solution {
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */
    public ArrayList<String> restoreIpAddresses(String s) {
        // Write your code here
        ArrayList<String> rst = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) {
            return rst;
        }

        StringBuilder sb = new StringBuilder();
        helper(rst, sb, s, 0, 0);

        return rst;

    }

    private void helper(ArrayList<String> rst, StringBuilder sb, String s,
                        int start, int count) {

        if (sb.length() == s.length() + 4 && count == 4) {
            sb.deleteCharAt(sb.length() - 1);
            rst.add(new String(sb));
            sb.append(".");
            return;
        }

        String tmp = s.substring(start, s.length());
        int length = sb.length();
        for (int i = 1; i < 4 && i <= tmp.length(); i++) {
            String sub = tmp.substring(0, i);
            if (isValid(sub)) {
                count++;
                sb.append(sub);
                sb.append(".");
                helper(rst, sb, s, start + i, count);
                sb.setLength(length);
                count--;
            }
        }
    }

    private boolean isValid(String s){

        if(s.charAt(0) == '0')
            return s.equals("0"); // to eliminate cases like "00", "10"
        int digit = Integer.valueOf(s);
        return digit >= 0 && digit <= 255;
    }
}

Palindrome partitioning:

• O(n * 2^n)
• add cache, similar to Word Break ii

public class Solution {
    /**
     * @param s: A string
     * @return: A list of lists of string
     */
     public List<List<String>> partition(String s) {
         List<List<String>> rst = new ArrayList<>();
         if (s == null || s.length() == 0) {
             return rst;
         }

         List<String> list = new ArrayList<>();
         helper(rst, list, s, 0);

         return rst;
     }

     private void helper(List<List<String>> rst, List<String> list, String s, int start) {

         if (start == s.length()) {
             rst.add(new ArrayList(list));
             return;
         }

         String temp = s.substring(start, s.length());

         for (int i = 1; i <= temp.length(); i++) {
             String sub = temp.substring(0, i);
             if (isPalindrome(sub)) {
                 list.add(sub);
                 helper(rst, list, s, start + i);
                 list.remove(list.size() - 1);
             }
         }

     }

    private boolean isPalindrome(String str) {

        int beg = 0 ;
        int end = str.length() - 1;

        while (beg < end) {
            if (str.charAt(beg) != str.charAt(end)) return false;
            beg++;
            end--;
        }
        return true;
    }

public class Solution {

    public List<List<String>> partition(String s) {
        // write your code here
        boolean[][] dp = initPalidrome(s);

        List<List<String>> rst = new ArrayList<>();
        List<String> list = new ArrayList<>();
        dfs(rst, list, dp, s, 0);
        return rst;
    }

    private void dfs(List<List<String>> rst, List<String> list, boolean[][] dp, String s, int pos) {

        if (pos == s.length()) {
            rst.add(new ArrayList<>(list));
            return;
        }

        for (int i = pos; i < s.length(); i++) {

            if (dp[pos][i]) {
                list.add(s.substring(pos, i+1));
                dfs(rst, list, dp, s, i+1);
                list.remove(list.size() - 1);
            }
        }
    }

    private boolean[][] initPalidrome(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }

        for (int i = 0; i < s.length() - 1; i++) {
            dp[i][i+1] = s.charAt(i) == s.charAt(i+1);
        }

        for (int i = 2; i < s.length(); i++) {
            for (int j = 0; j <= i-2; j++) {
                dp[j][i] = dp[j+1][i-1] && s.charAt(i) == s.charAt(j);
            }
        }

        return dp;
    }
}

Letter Combinations of a Phone Number

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {

        String[] combinations = {"0", "1", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

        ArrayList<String> rst = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return rst;
        }

        StringBuilder sb =new StringBuilder();
        helper(rst, sb, combinations, digits, 0);

        return rst;
    }

    private void helper(ArrayList<String> rst, StringBuilder sb, String[] combinations, String digits, int start) {

        if (sb.length() == digits.length()) {
            rst.add(new String(sb));
            return;
        }

        int pos = Character.getNumericValue(digits.charAt(start));
        String str = combinations[pos];

        for (int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            helper(rst, sb, combinations, digits, start + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

combination sum iv

word search

• o(4^n), n = length(word)
• grid, i, j, word, pos

public class Solution {
    public boolean exist(char[][] board, String word) {
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int row, int col) {
        if(index == word.length()) return true;
        if(row < 0 || row >= board.length) return false;
        if(col < 0 || col >= board[0].length) return false;
        if(board[row][col] != word.charAt(index)) return false;  

        board[row][col] = '#';

        boolean rst = (
            dfs(board, word, index + 1, row - 1, col) ||
            dfs(board, word, index + 1, row + 1, col) ||
            dfs(board, word, index + 1, row, col + 1) ||
            dfs(board, word, index + 1, row, col - 1)
                      );

        board[row][col] = word.charAt(index);

        return rst;
    }
}

number of islands

public class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i , j);
                    count ++;
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int x, int y){
        if(x < 0 || x >= grid.length) return;
        if(y < 0 || y >= grid[0].length) return;

        if(grid[x][y] == '0') return;

        grid[x][y] = '0';

        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }
}

n queen:

• (board[i][j] == 'Q' && (x == i || x+y == i+j || x+j == i+y)) // to check its diagonal and row
• in validation, only cares its left side, since the dfs use col to fill from left to right.
• improvement: use boolean[] or HashSet in validation , reduce validate from O(n^2) to O(1)
  • https://soulmachine.gitbooks.io/algorithm-essentials/java/dfs/n-queens.html
• T(n) = n*T(n-1) + O(n^2), 因此时间复杂度是O(n!)。

class Solution {
    public List<List<String>> solveNQueens(int n) {        
        char[][] board = new char[n][n];
        List<List<String>> rst = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        dfs(board, 0, rst);                
        return rst;
    }

    private void dfs(char[][] board, int col, List<List<String>> rst) {        
        if (col == board.length) {
            rst.add(drawBoard(board));
            return;
        }

        for (int i = 0; i < board.length; i++) {
            if (isValid(i, col, board)) {
                board[i][col] = 'Q';
                dfs(board, col + 1, rst);
                board[i][col] = '.';                    
            }            
        }                
    }

    private boolean isValid(int x, int y, char[][] board) {        
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < y; j++) {
                if (board[i][j] == 'Q' && (x == i || x+y == i+j || x+j == i+y)) return false;                    
            }
        }        
        return true;        
    }

    private List<String> drawBoard(char[][] board) {
        List<String> rst = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String temp = new String(board[i]);
            rst.add(temp);
        }
        return rst;
    }
}

class Solution {

    Set<Integer> row = new HashSet<>();
    Set<Integer> diag1 = new HashSet<>();
    Set<Integer> diag2 = new HashSet<>();

    public List<List<String>> solveNQueens(int n) {   

        char[][] board = new char[n][n];
        List<List<String>> rst = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }

        dfs(board, 0, rst);                
        return rst;
    }

    private void dfs(char[][] board, int col, List<List<String>> rst) {        
        if (col == board.length) {
            rst.add(drawBoard(board));
            return;
        }

        for (int i = 0; i < board.length; i++) {
            if (isValid(i, col, board)) {
                board[i][col] = 'Q';
                row.add(i); diag1.add(i+col); diag2.add(i-col);
                dfs(board, col + 1, rst);
                board[i][col] = '.';                    
                row.remove(i); diag1.remove(i+col); diag2.remove(i-col);
            }            
        }                
    }

    private boolean isValid(int x, int y, char[][] board) {
        return (!row.contains(x) && !diag1.contains(x+y) && !diag2.contains(x-y)); 
    }

    private List<String> drawBoard(char[][] board) {
        List<String> rst = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            String temp = new String(board[i]);
            rst.add(temp);
        }
        return rst;
    }
}

n queens ii:

• T(n) = n*T(n-1) + O(1), 因此时间复杂度是O(n!)。

class Solution {

    int count = 0;
    public int totalNQueens(int n) {

        boolean[] row = new boolean[n];
        boolean[] diag1 = new boolean[2*n];  // \
        boolean[] diag2 = new boolean[2*n];  // \

        dfs(row, diag1, diag2, n, 0);

        return count;        
    }

    private void dfs(boolean[] row, boolean[] diag1, boolean[] diag2, int n, int col) {
        if (col == n) {
            count++;
        }

        for (int i = 0; i < n; i++) {
            if (row[i] || diag1[i-col+n] || diag2[i+col]) continue;

            row[i] = diag1[i-col+n] = diag2[i+col] = true;
            dfs(row, diag1, diag2, n, col + 1);
            row[i] = diag1[i-col+n] = diag2[i+col] = false;;            
        }
    }
}