Number of Islands, Word Search, Word Search II, Implement Trie (Prefix Tree)

Posted on 2015-09-15   |   In 刷题   |  

Update—Leetcode now includes this problem:

Number of Islands

Given a 2d grid map of ‘1’s (land) and ‘0’s (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.
Example 1:

1
2
3
4
5
11110
11010
11000
00000
Answer: 1

Example 2:

1
2
3
4
5
11000
11000
00100
00011
Answer: 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int numIslands(char[][] grid) {
    if(grid.length==0 || grid==null) return 0;
    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'){
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}
private void dfs(char[][] grid, int i, int j){
    if(i<grid.length && i>=0 & j<grid[0].length && j>=0 && grid[i][j]=='1'){
        grid[i][j]='0';
        dfs(grid, i-1,j);
        dfs(grid, i+1,j);
        dfs(grid, i,j-1);
        dfs(grid, i,j+1);
    }
    return;
}

CountIslands/Floodfill

给定matrix，只有0和1，求1的连通size，连通只算上下左右，不算对角线

1
2
3
4
0 1 0 0 1 
1 1 1 0 0
1 0 0 0 1
0 0 0 0 1

Return 5， 1， 2

Solution

For each 1 in the matrix, recursivly search for the four neighbors, terminate if 0/boundary found.

  • Mark each node visited to avoid duplicated counting.
public ArrayList<Integer> countIslands(int[][] mat){
    int one,count;
    ArrayList<Integer> res = new ArrayList<Integer>();
    int[][] mark = new int[mat.length][mat[0].length];

    if(mat == null || mat.length == 0) return res;

    for (int i=0; i<mat.length; i++){
        for (int j=0; j<mat[0].length; j++){

            if(mark[i][j]!=1 && mat[i][j]==1){
                res.add(dfs(i,j, mat, mark));
            }
        }
    }
    return res;
}

public int dfs(int i, int j, int[][] mat, int[][] mark){
    if(i<0 || j<0 || i>mat.length-1 || j>mat[0].length-1 || mat[i][j]==0 || mark[i][j]==1)
        return 0;
    mark[i][j] = 1;
    return 1+dfs(i-1,j,mat,mark)+dfs(i+1,j,mat,mark)+dfs(i,j-1,mat,mark)+dfs(i,j+1,mat,mark);
}

public static void main(String[] args) {
    int[][] test = {{0, 1, 0, 0, 1} ,{1, 1, 1, 0, 0}, {1, 0, 0, 0, 1}, {0, 0, 0, 0, 1}};
    countIslands c = new countIslands();
    System.out.println(c.countIslands(test));
}

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,
Given board =

1
2
3
4
5
6
7
8
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static  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, i,j)){
					return true;
				}
			}
		}
		return false;
	}
	private static boolean dfs(char[][] a, String word, int i, int j){
		if(word.equals("")) return true;
		if(i<0 || j<0 ||j>=a[0].length || i>=a.length ) return false;
		if(a[i][j]==word.charAt(0)){
			char tmp=a[i][j];
			a[i][j]='#';
			boolean res = (dfs(a, word.substring(1), i+1, j) || dfs(a, word.substring(1), i, j+1) || dfs(a, word.substring(1), i-1, j) || dfs(a, word.substring(1), i, j-1));
			if(res) return true;
			else a[i][j]=tmp;
		}
		return false;
	}

Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must 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 in a word.
For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

1
2
3
4
5
6
7
8
9
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
Return ["eat","oath"].
Note:
You may assume that all inputs are consist of lowercase letters a-z.

DFS Solution

  • LTE… 
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
public List<String> findWords(char[][] board, String[] words) {
    List<String> res= new ArrayList<String>();
   	for(String s : words){
   		if(exist(board, s)){
   			res.add(s);
   		}
   	}
   	return res;
   }
   
   public static boolean exist(char[][] board, String word) {
       boolean[][] visited= 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(board[i][j]==word.charAt(0)){
   				if(dfs(board, word, i,j, visited)){
   					return true;
   				}
		    }
		}
	}
	return false;
}
private static boolean dfs(char[][] a, String word, int i, int j, boolean[][] visited){
	if(word.equals("")) return true;
	if(i<0 || j<0 ||j>=a[0].length || i>=a.length ) return false;
	if(a[i][j]==word.charAt(0) && !visited[i][j]){
		visited[i][j]=true;
		boolean res = (dfs(a, word.substring(1), i+1, j, visited) || dfs(a, word.substring(1), i, j+1, visited) || dfs(a, word.substring(1), i-1, j, visited) || dfs(a, word.substring(1), i, j-1, visited));
		if(res) return true;
		else visited[i][j]=false;
	}
	return false;
}

Trie Solution

  • Trie helps with worst case ([“aaaaaa…aaas”, “aaaaaaa..aaaay”…])
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class Solution {
    public class TrieNode{
        public boolean isWord = false;
        public TrieNode[] child = new TrieNode[26];
        public TrieNode(){
        }
    }
    TrieNode root = new TrieNode();
    boolean[][] flag;
    public List<String> findWords(char[][] board, String[] words) {
        Set<String> result = new HashSet<>();
        flag = new boolean[board.length][board[0].length];
        addToTrie(words);
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(root.child[board[i][j] - 'a'] != null){
                    search(board, i, j, root, "", result);
                }
            }
        }
        return new LinkedList<>(result);
    }
    private void addToTrie(String[] words){
        for(String word: words){
            TrieNode node = root;
            for(int i = 0; i < word.length(); i++){
                char ch = word.charAt(i);
                if(node.child[ch - 'a'] == null){
                    node.child[ch - 'a'] = new TrieNode();
                }
                node = node.child[ch - 'a'];
            }
            node.isWord = true;
        }
    }
    private void search(char[][] board, int i, int j, TrieNode node, String word, Set<String> result){
        if(i >= board.length || i < 0 || j >= board[i].length || j < 0 || flag[i][j]){
            return;
        }
        if(node.child[board[i][j] - 'a'] == null){
            return;
        }
        flag[i][j] = true;
        node = node.child[board[i][j] - 'a'];
        if(node.isWord){
            result.add(word + board[i][j]);
        }
        search(board, i-1, j, node, word + board[i][j], result);
        search(board, i+1, j, node, word + board[i][j], result);
        search(board, i, j-1, node, word + board[i][j], result);
        search(board, i, j+1, node, word + board[i][j], result);
        flag[i][j] = false;
    }
}

Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.

Solution

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
49
50
51
52
class TrieNode {
    // Initialize your data structure here.
    public boolean isword;
    public TrieNode[] children = new TrieNode[26];
    public TrieNode() {}
}
public class Trie {
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode r=root;
        for(int i=0;i<word.length();i++){
            if(r.children[word.charAt(i)-'a']==null){
                r.children[word.charAt(i)-'a']=new TrieNode();
            }
            r=r.children[word.charAt(i)-'a'];
        }
        r.isword=true;
    }
    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode r=root;
        for(int i=0;i<word.length();i++){
            if(r.children[word.charAt(i)-'a']==null) return false;
            r=r.children[word.charAt(i)-'a'];
        }
        return r.isword;
    }
    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode r=root;
        for(int i=0;i<prefix.length();i++){
            if(r.children[prefix.charAt(i)-'a']==null) return false;
            r=r.children[prefix.charAt(i)-'a'];
        }
        return true;
    }
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
#DFS #Recursion #Trie
Sort List, Insertion Sort List, Reverse Linked List, Palindrome Linked List, Delete Node in a Linked List, Remove Linked List Elements, Intersection of Two Linked Lists, Reorder List, Copy List with Random Pointer
Spiral Matrix, Spiral Matrix II, Search a 2D Matrix, Search a 2D Matrix II, Set Matrix Zeroes, Pascal's Triangle, Pascal's Triangle II