Word Search II
给一个2d数组, 里面是字符, 然后一个一个字符串数组, 里面是要找的字符串, 问那些能用2d数组里的字符拼起来. 这个题是最常考的题, 如果能直接用Trie还可以, 如果不能…..面试怕是直接挂了. 题目本身就是Trie的基础应用.
|
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
public class Solution { Set<String> res = new HashSet<String>(); public List<String> findWords(char[][] board, String[] words) { Trie trie = new Trie(); for (String word : words) { trie.insert(word); } int m = board.length; int n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { dfs(board, visited, "", i, j, trie); } } return new ArrayList<String>(res); } public void dfs(char[][] board, boolean[][] visited, String str, int x, int y, Trie trie) { if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) return; if (visited[x][y]) return; str += board[x][y]; if (!trie.startsWith(str)) return; if (trie.search(str)) { res.add(str); } visited[x][y] = true; dfs(board, visited, str, x - 1, y, trie); dfs(board, visited, str, x + 1, y, trie); dfs(board, visited, str, x, y - 1, trie); dfs(board, visited, str, x, y + 1, trie); visited[x][y] = false; } class TrieNode { public boolean endPoint; public TrieNode[] next; public TrieNode() { endPoint = false; next = new TrieNode[26]; } } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } // Inserts a word into the trie. public void insert(String word) { if(word != null) { TrieNode tmp = root; for(int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(tmp.next[c-'a'] == null) tmp.next[c-'a'] = new TrieNode(); tmp = tmp.next[c-'a']; } tmp.endPoint = true; } } // Returns if the word is in the trie. public boolean search(String word) { if(word == null) return false; TrieNode tmp = root; for(int i = 0; i < word.length(); i++) { char c = word.charAt(i); if(tmp.next[c-'a'] == null) return false; else tmp = tmp.next[c-'a']; } return tmp.endPoint; } // Returns if there is any word in the trie // that starts with the given prefix. public boolean startsWith(String prefix) { if(prefix == null) return false; TrieNode tmp = root; for(int i = 0; i < prefix.length(); i++) { char c = prefix.charAt(i); if(tmp.next[c-'a'] == null) return false; else tmp = tmp.next[c-'a']; } return true; } } } |