Word Search

DFS.

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        if (word == null || word.length() == 0) return true;
        
        boolean[][] used = new boolean[board.length][board[0].length];
        
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                if (helper(board, used, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    
    public boolean helper(char[][] board, boolean[][] used, String word, int validNum, int i, int j){
        if (validNum == word.length()) return true;
        
        if ( board[i][j] == word.charAt(validNum) && used[i][j] == false){
            validNum++;
            used[i][j] = true;
            boolean a = (validNum == word.length());
            if (i-1 >= 0){
                a |=  helper(board, used, word, validNum, i-1, j);
            }
            if (i+1 < board.length){
                 a |=  helper(board, used, word, validNum, i+1, j);
            }
            if (j-1 >= 0){
                 a |=  helper(board, used, word, validNum, i, j-1);
            }
            if (j+1 < board[0].length){
                 a |=  helper(board, used, word, validNum, i, j+1);
            }
            if (a == false){
                validNum --;
                used[i][j] = false;
            }
            return a;
        }
        return false;
    }
}

[LeetCode java Solution] – Backtracking/ Array/ Bit Manipulation – Subsets

Problem:

Given a set of distinct integers, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Method:

Thoughts:

Get all results for 0 element;

Get all results for 1 element;

Get all results for 2 elements;

…

Get all results for nums.length elements;

Since the result is non-descending, we have a sequence of iterating and we must find the right element to start from.

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        
        ArrayList<ArrayList<Integer>> r = new ArrayList<ArrayList<Integer>>(); // this is for return value;
        ArrayList<ArrayList<Integer>> res_pre = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> item = new ArrayList<Integer>();
        res_pre.add(item);
        if (nums == null || nums.length == 0) return res_pre;
        r.addAll(res_pre);
        
        Arrays.sort(nums);

        for (int i = 0; i < nums.length;i++){
            ArrayList<ArrayList<Integer>> newRes = new ArrayList<ArrayList<Integer>>();
            for (ArrayList<Integer> m: res_pre){
                ArrayList<Integer> newItem = new ArrayList<Integer>(m);
                int j = 0;
                // the conditions are easy to make mistakes.
                while( newItem.size() != 0  && j < nums.length && nums[j] <= newItem.get(newItem.size()-1) ){ 
                   j++;
                }
                for (; j< nums.length; j++){
                    newItem.add(nums[j]);
                    newRes.add(new ArrayList<Integer>(newItem));
                    newItem.remove(newItem.size()-1);
                }
            }
            r.addAll(newRes);
            res_pre = newRes;
        }
        return r;
    }
}

[LeetCode Java solution] – Backtracking – Combinations

Problem:

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Method:

Compare this one with the permutation problem, the differences are the following:

1) We don’t need to keep an array of used element, since combination does not care sequence.

2) But we do not iterate every element from 1 to n, instead, we iterate from the last element in ‘item’.

3) Very Important!!!! When adding to res, do remember to copy the element instead of just copy the reference.

Code:

public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (k <= 0 || n <= 0)  return res;
        ArrayList<Integer> item = new ArrayList<Integer>();
       
        return helper(n, k, item,res);
    }
    
    public ArrayList<ArrayList<Integer>> helper(int n, int left, ArrayList<Integer> item,  ArrayList<ArrayList<Integer>> res){
        
        if (left == 0){
            res.add(new ArrayList<Integer>(item));
            return res;
        }
        
        int i;
        if (item.size() == 0){
            i = 1;
        }else{
            i = item.get(item.size()-1) + 1;
        }
        
        for (; i <= n; i++){
                item.add(i);
                helper(n, left-1, item, res);
                item.remove(item.size()-1);
        }
        return res;
    }
}

[LeetCode Java Solution] – Backtracking – Permutations

Problem:

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Method 1:

Backtracking. This is a NP problem. We use recursive loop to solve it. Before recursive method, add sth. But after the recursion method, we need to protect the scene and remove what had been added.

Code for method 1:

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] nums) {
        ArrayList<Integer> item = new ArrayList<Integer>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> used = new ArrayList<Integer>();
        if (nums.length == 0) return res;
        return helper(res, item, used, nums);
    }
    
    public ArrayList<ArrayList<Integer>> helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> item, ArrayList<Integer> used, int[] nums){
        if (item.size() == nums.length){
            res.add(new ArrayList<Integer>(item));  // this is important. can not to be res.add(item), since we still keep the reference to item and may change it in the future.
            return res;
        }
        
        for (int i = 0; i < nums.length; i++){
            if (!used.contains(nums[i])){
                item.add(nums[i]);
                used.add(nums[i]);
                helper(res, item, used, nums);
                item.remove(item.size()-1);
                used.remove(used.size()-1);
            }
        }
        return res;
        
    }
    
}

Method 2:

Iterative method.

For 1 element, get all possible combinations.

For 2 elements, get all possible combinations.

….

For all elements, get all possible combinations.

Code for method 2:

public class Solution {
    public ArrayList< ArrayList<Integer>> permute(int[] nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (nums == null || nums.length == 0) return res;
        ArrayList<Integer> item = new ArrayList<Integer>();
        item.add(nums[0]);
        res.add(item);
        
        for (int i = 1; i < nums.length; i++){
            ArrayList<ArrayList<Integer>> newres = new ArrayList<ArrayList<Integer>>();
            for (int j = 0; j < res.size(); j++){
                ArrayList<Integer> temp = res.get(j);
                for (int k = 0; k < temp.size() + 1; k++){
                    ArrayList<Integer> newItem = new ArrayList<Integer>(temp);
                    newItem.add(k,nums[i]);
                    newres.add(newItem);
                }
            }
            res = newres;
        }
        return res;
    }
}