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] Two Sum

Problem:

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Method 1: O(n^2)

Use two for loop to check every combination.

Node that we need to put one return statement both inside and outside of the condition clause.

Code for method 1:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for (int i = 0; i < nums.length -1; i++){
                for (int j = i+1; j < nums.length; j++){
                    if (nums[i]+nums[j] == target){
                        res[0] = i+1;
                        res[1] = j+1;
                        return res;
                    }
                }
        }
        return res;
    }
}

Method 2: O(n)

Use hash table. Key: the number that I am looking for. Value: the previous index.

Code for method 2:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        HashMap<Integer, Integer> dict = new HashMap<Integer, Integer>();
        dict.put (target-nums[0], 0);
        for (int i = 1; i < nums.length; i++){
            if (dict.containsKey(nums[i])){
                res[0] = dict.get(nums[i]) + 1;
                res[1] = i + 1;
                return res;
            }else{
                dict.put(target-nums[i],i);
            }
        }
        return res;
    }
}

Method 3: O(nlogn)

Use two pointer.

Be careful about finding the indexes after getting the right numbers.

Code for method 3:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        int low = 0;
        int high = nums.length - 1;
        
        int[] copy = new int[nums.length];
        System.arraycopy(nums,0, copy, 0,nums.length);
        Arrays.sort(copy);
        
        while( copy[low] + copy[high] != target ){
            if (copy[low] + copy[high] > target){
                high --;
            }else{
                low ++;
            }
        }
        
        for (int i = 0; i < nums.length; i++){
            if (nums[i] == copy[low] || nums[i] == copy[high]){
                if (res[0] == 0){
                    res[0] = i+1;
                }else{
                    res[1] = i+1;
                }
            }
        }
        
        Arrays.sort(res);
        
        return res;
    }
}

[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] – Array/ Two Pointers – Remove Element

Problem:

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Method 1: 

Swap the element with given value with the last element in the array. Keep track of the last element in the array.

Code for method 1:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0 ) return 0;
        
        int length = nums.length;// the index where to put the extra element
        int curIdx = 0; // the current index in the array
        
        
        while (curIdx < length ){
            if (nums[curIdx] == val ){
                nums[curIdx] = nums[length-1];
                length--;
            }else{
                curIdx ++;
            }
        }
        return length;
    }
}

Method 2:

Updating the array from left to right use two pointers. Only remain non-val elements.

Code for method 2:

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        int i = 0;// old array
        int j = 0;// new array
        
        while (i < nums.length){
            if (nums[i] != val){
                nums[j] = nums[i];
                j++;
            }
            i++;
        }
        return j;
    }
}

[LeetCode]- Array – Set Matrix Zeroes

Problem:

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

Method:

The most space effective method is to use the first row and first column to store whether the row or the column needs to be set to 0. However, we need two boolean to indicate wether the first row or the first column themselves need to be reset.

Code:

public class Solution {
    public void setZeroes(int[][] matrix) {
        int height = matrix.length;
        int width = matrix[0].length;
        
        if (height == 0 || width == 0) return;
        
        boolean first_row = false;
        boolean first_col = false;
      
        for (int i = 0; i < width ;i++){
            if (matrix[0][i] == 0){
                first_row = true;
                break;
            //    matrix[0][i] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < height; i++){
            if (matrix[i][0] == 0){
                first_col = true;
                break;
            //    matrix[i][0] = Integer.MAX_VALUE;
            }
        }
        
        for (int i = 1; i < height; i++){
            for (int j = 1; j < width; j++){
                if (matrix[i][j] == 0){
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        
        for (int i = 1; i < width; i++){
            if (matrix[0][i] == 0){
                // set that col to 0
                for (int m = 1; m < height; m++){
                    matrix[m][i] = 0;
                }
            }
        }
        for (int j = 1; j < height; j++){
            if (matrix[j][0] == 0){
                // set that row to 0
                for (int n = 1; n < width; n++){
                    matrix[j][n] = 0;
                }
            }
        }
        
        if (first_row){
            // set first row = 0;
            for (int i = 0; i < width; i++){
                matrix[0][i] = 0;
            }
        }
        if (first_col){
            //set first col = 0;
            for (int j = 0; j < height;j++){
                matrix[j][0] = 0;
            }
        }
        
    }
}