Word Search Problem with Trie Solution
5601 ワード
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 =
Return
各エントリ(0<=i
trieがあれば、深さ優先アルゴリズムを通過します.
ここで注意すべき点は、生成された文字列が要求を満たしている(すなわち、配列内の文字列と一致している)ことを確認した場合、検索を終了することはできません.そうしないと、結果が失われます.例えば、上記のテストに使用された例では、aaaとaaabが条件に合致し、aaaが先に見つかり、戻ったらaaabが失われます.
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"] . 各エントリ(0<=i
class TrieNode {
private TrieNode[] children;
private boolean end = false;
// Initialize your data structure here.
public TrieNode() {
this.children = new TrieNode[26];
}
public void insert(char[] words, int i) {
if (i >= words.length - 1) {
this.end = true;
return;
}
int j = i + 1;
char nxt = words[j];
TrieNode child = children[nxt - 'a'];
if (child == null) {
child = new TrieNode();
children[nxt - 'a'] = child;
}
child.insert(words, j);
}
public boolean startsWith(char[] words, int i) {
if(i >= words.length - 1) {
return true;
}
int j = i + 1;
char nxt = words[j];
TrieNode child = children[nxt - 'a'];
if(child == null) {
return false;
}
return child.startsWith(words, j);
}
public boolean search(char[] words, int i) {
if(i >= words.length - 1) {
return this.end;
}
int j = i + 1;
char nxt = words[j];
TrieNode child = children[nxt - 'a'];
if(child == null) {
return false;
}
return child.search(words, j);
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
root.insert(word.toCharArray(), -1);
}
// Returns if the word is in the trie.
public boolean search(String word) {
return root.search(word.toCharArray(), -1);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
return root.startsWith(prefix.toCharArray(), -1);
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.insert("ab");
System.out.println(trie.search("a"));
System.out.println(trie.startsWith("a"));
}
} trieがあれば、深さ優先アルゴリズムを通過します.
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
/**
* Created by senyuanwang on 15/5/19.
*/
public class Solution {
static int[] dx = new int[]{-1, 0, 0, 1};
static int[] dy = new int[]{0, -1, 1, 0};
public static void visit(char[][] board, boolean[][] checked, int i, int j, Trie trie, String path, Set<String> result) {
if (trie.search(path)) {
result.add(path);
// return;
}
if (!trie.startsWith(path)) {
return;
}
for (int k = 0; k < 4; k++) {
int x = dx[k] + i;
int y = dy[k] + j;
if (x >= 0 && x < board.length && y >= 0 && y < board[0].length && !checked[x][y]) {
checked[x][y] = true;
visit(board, checked, x, y, trie, path + board[x][y], result);
checked[x][y] = false;
}
}
}
public static List<String> findWords(char[][] board, String[] words) {
Trie trie = new Trie();
for (String word : words) {
trie.insert(word);
}
boolean[][] checked = new boolean[board.length][board[0].length];
Set<String> result = new HashSet<String>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
checked[i][j] = true;
visit(board, checked, i, j, trie, "" + board[i][j], result);
checked[i][j] = false;
}
}
List<String> list = new ArrayList<String>(result.size());
for (String str : result) {
list.add(str);
}
return list;
}
public static void main(String[] args) {
char[][] board = {
{'a', 'a'}, {'a', 'b'}};
String[] words = {"aba", "baa", "bab", "aaab", "aaa", "aaaa", "aaba"};
System.out.println(findWords(board, words));
}
}ここで注意すべき点は、生成された文字列が要求を満たしている(すなわち、配列内の文字列と一致している)ことを確認した場合、検索を終了することはできません.そうしないと、結果が失われます.例えば、上記のテストに使用された例では、aaaとaaabが条件に合致し、aaaが先に見つかり、戻ったらaaabが失われます.