LeetCode Problem: Search Topics

algorithm

LeetCode Problem: Search Topics

The word search problem is like this:

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. For example:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

word_search_1

The word search problem is similarly to the number of islands problem. What we need to do is to look through the grid, and once we find the first letter of the word, we need to DFS the surrounding letters.

Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class WordSearch {
    public boolean exist(char[][] board, String word) {
        // Traverse the board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                // Once we find the first letter of the word, we begin DFS.
                if (board[i][j] == word.charAt(0) && dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    public boolean dfs(char[][] board, int i, int j, String word, int index) {
        if (index == word.length()) {
            return true;
        }

        if (i < 0 || i >= board.length || j < 0 || j >= board[i].length || board[i][j] != word.charAt(index)) {
            return false;
        }

        // The same letter cell may not be used more than once.
        // Therefore, we temporally "erase" the current letter.
        char temp = board[i][j];
        board[i][j] = ' ';
        // Search up, down, right, left
        boolean result = dfs(board, i - 1, j, word, index + 1) ||
                dfs(board, i + 1, j, word, index + 1) ||
                dfs(board, i, j - 1, word, index + 1) ||
                dfs(board, i, j + 1, word, index + 1);
        board[i][j] = temp;

        return result;
    }
}

The process of the above code is like this:

2. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

letter_combinations_of_a_phone_number

For example:

1
2
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.ArrayList;
import java.util.List;

public class LetterCombinationsOfAPhoneNumber {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if (digits.length() == 0) {
            return result;
        }

        String[] mapping = {
                " ",// 0
                " ",// 1
                "abc",// 2
                "def",// 3
                "ghi",// 4
                "jkl",// 5
                "mno",// 6
                "pqrs",// 7
                "tuv",// 8
                "wxyz"// 9
        };

        dfs(digits, mapping, result, "");
        return result;
    }

    public void dfs(String digits, String[] mapping, List<String> result, String current) {
        if (current.length() == digits.length()) {
            result.add(current);
            return;
        }

        String letters = mapping[digits.charAt(current.length()) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            dfs(digits, mapping, result, current + letters.charAt(i));
        }

    }
}

The process of the above code is like this:

3. Combination Sum

combination_sum

To solve the combination sum problem, we also use DFS. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<>();
        if (candidates.length == 0) {
            return results;
        }

        // We firstly sort the array.
        Arrays.sort(candidates);

        // Then we do DFS.
        List<Integer> combination = new ArrayList<>();
        dfs(candidates, target, results, combination, 0);

        return results;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> results, List<Integer> combination, int startIndex) {
        if (target == 0) {
            results.add(new ArrayList<>(combination));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
                return;
            }

            combination.add(candidates[i]);
            dfs(candidates, target - candidates[i], results, combination, i);
            combination.remove(combination.size() - 1);
        }

    }
}

4. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets. For example:

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.ArrayList;
import java.util.List;

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        dfs(nums, 0, new ArrayList<Integer>(), results);

        return results;
    }

    public void dfs(int[] nums, int index, List<Integer> combination, List<List<Integer>> results) {
        results.add(new ArrayList<>(combination));
        // We cannot write the above code like this:
        // results.add(combination);
        // Because every time we are adding the same reference.

        for (int i = index; i < nums.length; i++) {
            combination.add(nums[i]);
            dfs(nums, i + 1, combination, results);
            combination.remove(combination.size() - 1);
        }
    }
}

The process of the above code is like this:

5. Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array. Your algorithm’s runtime complexity must be in the order of O(log n).

1
2
3
4
5
6
7
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

As our algorithm must be in O(log n), we should find the pivot and do the binary search. Firstly we should understand what is binary search, here is the code for standard binary search:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 1. Using iteration
// Suppose the array nums is sorted in ascending order.
public int binarySearch(int[] nums, int target) {        
    int left = 0;
    int right = nums.length - 1;
        
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }

    return -1;
}

// ---------------------------------------------------------------
// 2. Using Recursion
// Suppose the array nums is sorted in ascending order.
public int binarySearch(int[] nums, int target) {
        return binarySearch(nums, target, 0, nums.length - 1);
    }

public int binarySearch(int[] nums, int target, int left, int right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) {
        return target;
    } else if (nums[mid] < target) {
        return binarySearch(nums, target, mid + 1, right);
    } else {
        return binarySearch(nums, target, left, mid - 1);
    }
}

For this problem, as we do not know the pivot beforehand, we can firstly find the maximum or minimum number in the array, then we can know where the pivot is. After finding out the pivot, we can use binary search to find the target.

We can find the minimum number in a sorted array like this:

Here is the code to find the minimum number:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 1. Using iteration
public int findMin(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return nums[left];
}

// -------------------------------------------
// 2. Using recursion
// Note that this code would cause StackOverflowError in Java.
public int findMin(int[] nums) {
    return findMin(nums, 0, nums.length - 1);
}
    
public int findMin(int[] nums, int left, int right) {
    if (left + 1 >= right) {// only 1 or 2 elements
        return Math.min(nums[left], nums[right]);
    }
        
    if (nums[left] < nums[right]) {// sorted
        return nums[left];
    }
        
    int mid = left + (left + right) / 2;
    int leftMin = findMin(nums, left, mid - 1);
    int rightMin = findMin(nums, mid, right);
        
    return Math.min(leftMin, rightMin);
}

Now, let’s go back to our original problem, searching a target number in rotated sorted array. Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package search;

public class SearchInRotatedSortedArray {
    public int search(int[] nums, int target) {
        if (nums.length == 0) {
            return -1;
        }

        // 1. We can firstly find the minimum number of the array, which
        // tells us where the pivot is.
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 2. After the while loop, right/left is the index of the minimum number. And 
        // we need to make sure which part we should use to find the target.
        int pivot = left;// or right
        left = 0;
        right = nums.length - 1;
        if (target >= nums[pivot] && target <= nums[right]) {
            left = pivot;
        } else {
            right = pivot;
        }

        // 3. We do the binary search to find the target.
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }

}

The process of the above code is like this:

6.Number of Islands

Given a 2d grid map of 1s (land) and 0s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

For example, if we have a grid like this:

1
2
3
4
11110
11010
11000
00000

The number of islands is 1:

num_of_islands

If we have a grid like this:

1
2
3
4
11000
11000
00100
00011

The number of islands is 3:

num_of_islands_2

To solve the problem, we need a counter to record the number of islands. At the beginning, the counter is set to 0. What we need to do is to traverse the grid, and once we find a land, we change this land to water(change 1 to 0). Then we search the surrounding lands and also change them to water. After we “merge” all the adjacent lands, we increase our counter and continue to traverse the grid.

Here is the code to solve the problem:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class NumberOfIslands {
    public static int numOfIslands(char[][] grid) {

        int numOfIslands = 0;// a counter to record the number of islands

        // traverse the grid
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                // once we find a land, we search and "merge" all its surrounding lands
                // and increase the counter by 1
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    numOfIslands++;
                }
            }
        }

        return numOfIslands;
    }

    // search all surround lands of land(i,j), and change them from 1 to 0
    public static void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0';
        dfs(grid, i - 1, j);// search up
        dfs(grid, i + 1, j);// search down
        dfs(grid, i, j - 1);// search left
        dfs(grid, i, j + 1); // search right
    }
    
    // main method to test the numOfIslands method.
    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}};

        System.out.println(numOfIslands(grid));
    }
}

Note that we use depth-first search(DFS) to search the surrounding lands, the process is like this: https://www.youtube.com/watch?v=l3nXH-G_f90