212. Word Search II

212. 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 =

[ ['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.

思路： 用trie树先把单词存起来，然后扫board，扫board的时候用trie树中的可能出现的单词作为限制条件，那么当扫到一个trie中结尾存在的单词时，把它存进result中去。

class Solution { class TrieNode { TrieNode[] next = new TrieNode[26]; String word; } public TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String word : words) { TrieNode p = root; for (char c : word.toCharArray()) { int i = c - 'a'; if (p.next[i] == null) p.next[i] = new TrieNode(); p = p.next[i]; } p.word = word; } return root; } public void dfs(List result, char[][] board, TrieNode p, int i, int j) { char c = board[i][j]; if (c == '#' || p.next[c - 'a'] == null) return; p = p.next[c - 'a']; if (p.word != null) { result.add(p.word); p.word = null; //去重 } board[i][j] = '#'; int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; for (int k = 0; k < dir.length; k++) { int x = i + dir[k][0], y = j + dir[k][1]; if (x < 0 || x > board.length - 1 || y < 0 || y > board[i].length - 1) continue; dfs(result, board, p, x, y); } board[i][j] = c; } public List findWords(char[][] board, String[] words) { List result = new ArrayList(); if (board == null || board.length == 0 || board[0].length == 0) return result; TrieNode root = buildTrie(words); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[i].length; j++) { dfs(result, board, root, i, j); } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。