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;
    }
}

Sqrt(x)

Method 1:
Binary Search

Code:

public class Solution {
    public int mySqrt(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        
        long low = 1;
        long high = x/2+1;
        
        while (low <= high){
            long mid = (low+high)/2;
            if (mid * mid == x) return (int) mid;
            else if (mid * mid < x){
                low = mid + 1;
            }else{
                high = mid -1;
            }
        }
    
        return (int)high;
        
    }
}

Another Method:

Newton method.

[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] -*** Recursion/DP – Scramble String

Problem:

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

Reference 1: http://blog.csdn.net/linhuanmars/article/details/24506703

Reference 2: http://www.cnblogs.com/springfor/p/3896164.html

Method 1: by recursive.

• Partition s1 as s11, s12; partition s2 as s21, s22. Then s11, s21 should be scramble and s12, s22 should be scramble; or s11, s22 are scramble and s12, s21 are scramble.
• To avoid the exceeding time limit. Check: 1) length equal? (If not, false) 2) They contain same elements? (if not, false)3) they are equal?(if yes, true)

Code for method 1:

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length()!= s2.length()) return false;
        if (s1.length() == 0) return s2.length() == 0;
        if (s1.equals(s2)) return true;
        // Pruning to pass it!
        char[] t1 = s1.toCharArray(), t2 = s2.toCharArray();
        Arrays.sort(t1);
        Arrays.sort(t2);
        if (!new String(t1).equals(new String(t2)))  return false;
        
        for (int i = 0; i < s1.length()-1; i++){
            //partition s1 into two pieces;
            String s11 = s1.substring(0,i+1);
            String s12 = s1.substring(i+1);
        
            String s21 = s2.substring(0,i+1);
            String s22 = s2.substring(i+1);
            if ((isScramble(s11,s21)&&isScramble(s12,s22) )) {
                return true;
            }
            
            s21 = s2.substring(s2.length()-i-1);
            s22 = s2.substring(0,s2.length()-i-1);
            if ((isScramble(s11,s21)&&isScramble(s12,s22) )) {
                return true;
            }
            
        }
        return false;
    }
}

Method 2:  by Dp 

Code for method 2:

[LeetCode] -*** Two pointers / KMP / Rolling hash – Implement strStr()

Problem:

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Knowledge Preparation:

1. strStr function. (Search String for Substring)  the strStr function searches within the string pointed to by s1 for the string pointed to by s2. It returns a pointer to the first occurrence in s1 of s2.

2.To make it easier, this problem is asking us to search the String ‘needle’ in the String ‘haystack’, and return the first occurrence of needle.

3. About corner case: strStr(Any String.””)  return 0;

Method 1: Brute Force

Use two pointers. If every character matches, then return the index, or continue to compare.

Several details:

1. Check the remaining length before comparison. It could significantly reduce the time.

2. First check if exceeding the length, then get the character. If the sequence is reversed, running time error (Out of boundary exception) may occur.

3. Do not forget corner case. strStr(Any String.””)  return 0;

Code for method 1:

public class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0 && haystack.length() == 0) return 0;
        if (needle == null  && haystack == null) return 0;
        if (needle == null || needle.length() == 0) return 0;

        if (haystack == null || haystack.length() == 0) return -1;

        int idx0 = 0; // record the starting index in haystack
        int idx1 = 0; // move through the haystack
        int idx2 = 0; // move throught the needle

        while (idx0 <= haystack.length()-needle.length()){
            // judging the length is very important! Or it won't pass
            idx1 = idx0;
            idx2 = 0;
            while (idx2 < needle.length() && idx1 < haystack.length() &&haystack.charAt(idx1) == needle.charAt(idx2)  ){
                idx1++;
                idx2++;
            }

            if (idx2 == needle.length()){
               return idx0;
            }else{
                idx0 ++;
            }
        }
        return -1;
    }
}

Another code for method 1:

The above code is not clear. To avoid dealing with edge cases separately, we could do the following:

public class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0;; i++){
            for (int j = 0;; j++){
                if (j == needle.length()) return i;
                if (i + j == haystack.length()) return -1;
                if (needle.charAt(j) != haystack.charAt(j+i)) break;
            }
        }
    }
}

Method 2: KMP method

KMP method is known to solve the problem of checking if one string is a substring of another one.

// This is the KMP solution
public class Solution {
    public int strStr(String haystack, String needle) {

        int i = 0;
        int hlength = haystack.length();
        int nlength = needle.length();

        if (nlength == 0) {
            return 0;
        } else {
            //get the prefix values for string: needle.
            int[] form = KMPform(needle);

            while (i <= hlength - nlength) {
                int j = 0;
                while (j < nlength) {
                    if (haystack.charAt(i + j) != needle.charAt(j)) {
                        if (j == 0) {
                            i++;
                        } else {
                            i = i + j - form[j - 1] - 1;
                        }
                        break;
                    } else if (j == nlength - 1) {
                        return i;
                    }
                    j++;
                }
            }

            return -1;
        }
    }

    public int[] KMPform(String str) {
        int[] form = new int[str.length()];
        form[0] = -1;
        for (int i = 1; i < form.length; i++) {
            int index = form[i - 1];
            while (index >= 0 && str.charAt(i) != str.charAt(index + 1))
            {
                index = form[index];
            }
            if (str.charAt(i) == str.charAt(index + 1))
            {
                form[i] = index + 1;
            }
            else
            {
                form[i] = -1;
            }
        }
        return form;
    }

}

[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] – String/Hashtable – Anagrams

Problem:

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Method:

Create a HashMap:

key: String (after chars are sorted);

value: The specific corresponding string.

Then, iterate through the HashMap. If there is a key with more than two values, we add them into the result container.

Code:

public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        if (strs == null || strs.length == 0) return null;
        ArrayList<String> res = new ArrayList<String>();
        
        HashMap<String, ArrayList<String>> dict = new HashMap<String, ArrayList<String>>();
        
        for (int i = 0; i < strs.length; i++){
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String s = new String(c);
            if (dict.containsKey(s)){
                dict.get(s).add(strs[i]);
            }else{
                ArrayList<String> l = new ArrayList<String>();
                l.add(strs[i]);
                dict.put(s,l);
            }
        }
        Iterator iter = dict.values().iterator();
        while(iter.hasNext()){
            ArrayList<String> temp = (ArrayList<String>)iter.next();  //cast type!!
            if(temp.size() > 1){
              res.addAll(temp);
            }
        }
        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;
    }
}

[LeetCode Java Solution] – sort/ two pointers/ merge- Merge k Sorted Lists

Problem:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Method 1:

MergeSort. This is a very typical implementation for MergeSort by using array.

Code for method 1:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return helper(lists, 0, lists.length-1);
    }
    
    public ListNode helper (ListNode[] lists, int l, int h){
        if (l < h){
             int mid = (l + h)/2;
             return merge(helper(lists, l, mid), helper(lists, mid+1, h));
        }
        return lists[l];
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                temp.next = l1;
                temp = temp.next;
                l1 = l1.next;
            }else{
                temp.next = l2;
                temp = temp.next;
                l2 = l2.next;
            }
        }
        if (l1 != null){
            temp.next = l1;
        }
        if (l2 != null){
            temp.next = l2;
        }
        return dummy.next;
    }
}

Analysis for time complexity:

Suppose there are k lists, and there are n elements inside each list. The time complexity is O(nklogk).

Method 2:

Use heap. Suppose we have k lists, and for each list, there are at most n elements.

Maintain a list of k elements. And always remove the first element from the list. After removing an element, add the element after it to the heap.

Code for method 2:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(10, new Comparator<ListNode>(){
            public int compare (ListNode l1, ListNode l2){
                return l1.val - l2.val;
            }
        });
        
        for (int i = 0; i < lists.length; i++){
            ListNode temp = lists[i];
            if (temp != null){
                heap.offer(temp);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        
        while (heap.size() != 0){
            ListNode n = heap.poll();
            cur.next = n;
            cur = cur.next;
            if (n.next != null){
                heap.offer(n.next);
            }
        }
        return dummy.next;
    }
}

Analysis for time complexity:

We have to insert at most k*n nodes, and for each node to be in order in the heap, we need log(k) time (“Bottom Up Insertion”). So total time complexity is also knlog(k).