1. Implement Trie Tree (Prefix Tree)
字典树： 根节点不包含字符， 除根节点以外每个结点只包含一个字符
framework
public class Trie {
/** Initialize your data structure here. */
public Trie() {
}
/** Inserts a word into the trie. */
public void insert(String word) {
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
}
}
class TrieNode {
boolean isWord;
TrieNode[] children = new TrieNode[26];
public TrieNode(){}
}
public class Trie {
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode p = root;
for(char w: word.toCharArray()){
if(p.children[w - 'a'] == null)
p.children[w - 'a'] = new TrieNode();
p = p.children[w - 'a'];
}
p.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode p = root;
for(char w: word.toCharArray()){
if(p.children[w - 'a'] == null)
return false;
p = p.children[w - 'a'];
}
return p.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode p = root;
for(char w: prefix.toCharArray()){
if(p.children[w - 'a'] == null)
return false;
p = p.children[w - 'a'];
}
return true;
}
}
2. Add and Search Word - Data structure design
Design a data structure that supports the following two operations:
void addWord(word)
bool search(word)
search(word) can search a literal word or a regular expression string containing only lettersa-zor.. A.means it can represent any one letter.
For example:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -
>
false
search("bad") -
>
true
search(".ad") -
>
true
search("b..") -
>
true
class TrieNode{
TrieNode[] children = new TrieNode[26];
boolean isWord;
public TrieNode(){}
}
public class WordDictionary {
TrieNode root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new TrieNode();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
TrieNode ps = root;
for(char w: word.toCharArray()){
if(ps.children[w-'a']==null){
ps.children[w-'a'] = new TrieNode();
}
ps = ps.children[w-'a'];
}
ps.isWord = true;
}
/** Returns if the word is in the data structure.
//A word could contain the dot character '.' to represent any one letter. */
public boolean search(String word) {
return match(word.toCharArray(), 0, root);
}
private boolean match(char[] chs, int k, TrieNode node) {
if (k == chs.length) return node.isWord;
if (chs[k] != '.') {
return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
}
else {
for (int i = 0; i < node.children.length; i++) {
if (node.children[i] != null) {
if (match(chs, k + 1, node.children[i])) {
return true;
}
}
}
}
return false;
}
}
3. Word Search
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,
Givenboard=
{
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
public class Solution {
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(search(board, i, j, word, 0))
return true;
}
}
}
return false;
}
public boolean search(char[][] board, int i, int j, String word, int k) {
if(k == word.length()) return true;
if(i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1 || board[i][j] != word.charAt(k))
return false;
board[i][j] = '*';
boolean res = (search(board, i - 1, j, word, k + 1) ||
search(board, i + 1, j, word, k + 1) ||
search(board, i, j - 1, word, k + 1) ||
search(board, i, j + 1, word, k + 1));
board[i][j] = word.charAt(k);
return res;
}
}
4. 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,
Givenwords=["oath","pea","eat","rain"]andboard=
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
Return
["eat","oath"]
class TrieNode{
TrieNode[] children = new TrieNode[26];
boolean isWord;
String item;
public TrieNode(){}
}
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTree(words);
List<String> ans = new ArrayList<>();
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
dfs(board, i, j, root, ans);
}
}
return ans;
}
public void dfs(char[][] board, int i, int j, TrieNode p, List<String> ans) {
if(i<0||i>board.length-1||j<0||j>board[0].length-1) return;
char c = board[i][j];
if(c=='*'||p.children[c-'a']==null) return;
p = p.children[c-'a'];
if(p.isWord){
ans.add(p.item);
p.isWord = false;
}
board[i][j] = '*';
dfs(board, i, j-1, p, ans);
dfs(board, i, j+1, p, ans);
dfs(board, i-1, j, p, ans);
dfs(board, i+1, j, p, ans);
board[i][j] = c;
}
public TrieNode buildTree(String[] words) {
TrieNode root = new TrieNode(), p;
for(String word: words){
p = root;
for(char w: word.toCharArray()){
if(p.children[w-'a']==null)
p.children[w-'a'] = new TrieNode();
p = p.children[w-'a'];
}
p.isWord = true;
p.item = word;
}
return root;
}
}