基础知识
- When inserting a word into the Trie pay attention to where the root node was at , move the reference not the root Trie node itself.
Perfect for dealing with common prefixs
208. Implement Trie (Prefix Tree)
实现Trie的基本操作 自己写了一个感觉很冗长 如果是实现Trie的很多功能还是考虑封装好在一个Class里面
/**
* Your Trie object will be instantiated and called as such:
* Trie trie = new Trie();
* trie.insert("lintcode");
* trie.search("lint"); will return false
* trie.startsWith("lint"); will return true
*/
class TrieNode {
// Initialize your data structure here.
public TrieNode[] children;
public boolean hasWord;
public TrieNode() {
this.children = new TrieNode[26];
this.hasWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
//important
TrieNode p = root;
char[] arr = word.toCharArray();
for(int i = 0;i < arr.length;i++){
char cur = arr[i];
if(p.children[cur - 'a'] == null){
p.children[cur - 'a'] = new TrieNode();
}
p = p.children[cur - 'a'];
}
p.hasWord = true;
}
//traverse down the word and return the final character place
public TrieNode find(String word){
TrieNode p = root;
for(int i = 0;i < word.length();i++){
char cur = word.charAt(i);
if(p.children[cur - 'a'] != null){
p = p.children[cur - 'a'];
}
else{
return null;
}
}
return p;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode p = find(word);
return (p != null && p.hasWord);
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
return (find(prefix) != null);
}
}
211. Add and Search Word - Data structure design
利用Trie Search的例子 注意的是因为 '.' 可以代表任何字符 所以这个题用recursion写会好一些
class TrieNode {
public TrieNode[] children;
public boolean hasWord;
public TrieNode() {
children = new TrieNode[26];
hasWord = false;
}
}
public class WordDictionary {
private TrieNode root;
public WordDictionary(){
root = new TrieNode();
}
// Adds a word into the data structure.
public void addWord(String word) {
// Write your code here
TrieNode now = root;
for(int i = 0; i < word.length(); i++) {
Character c = word.charAt(i);
if (now.children[c - 'a'] == null) {
now.children[c - 'a'] = new TrieNode();
}
now = now.children[c - 'a'];
}
now.hasWord = true;
}
boolean find(String word, int index, TrieNode now) {
if(index == word.length()) {
return now.hasWord;
}
Character c = word.charAt(index);
if (c == '.') {
for(int i = 0; i < 26; ++i)
if (now.children[i] != null) {
if (find(word, index+1, now.children[i]))
return true;
}
return false;
} else if (now.children[c - 'a'] != null) {
return find(word, index+1, now.children[c - 'a']);
} else {
return false;
}
}
425. Word Squares
Build the square while validating whether the result is correct by checking the prefix of the word that qualifies. During each round, the prefix to be checked is different, dynamically changed. What is the best way to retrieve all the words with a specific matrix in a dictionary of words--- Trie Data Structure
这个解法可能包含了重复结果 ! 对于Trie怎么实简洁一点 每次都是分开写TrieNode 然后用char的index定位children
public class Solution {
class TrieNode {
List<String> list;
TrieNode[] children;
public TrieNode(){
list = new ArrayList<String>();
children = new TrieNode[26];
}
}
class Trie{
public TrieNode root;
//Build the Trie Tree from a list of Strings
public Trie(String[] words){
this.root = new TrieNode();
for(String s : words){
TrieNode cur = root;
for(char c : s.toCharArray()){
int index = c - 'a';
if(cur.children[index] == null){
cur.children[index] = new TrieNode();
}
cur.list.add(s);
cur = cur.children[index];
}
}
}
//find the list of strings with a given index
public List<String> getPrefix(String prefix){
List<String> result = new ArrayList();
TrieNode cur = root;
for(char c : prefix.toCharArray()){
int index = c - 'a';
if(cur.children[index] == null){
return result;
}
cur = cur.children[index];
}
result.addAll(cur.list);
return result;
}
}
//
public List<List<String>> wordSquares(String[] words) {
List<List<String>> result = new ArrayList();
if(words == null || words.length == 0)return result;
//the number of words should appear in the final result
int n = words.length;
Trie trie = new Trie(words);
List<String> cur = new ArrayList<String>();
for(String s:words){
cur.add(s);
helper(result,trie,words,cur);
cur.remove(s);
}
return result;
}
public void helper(List<List<String>> result,Trie dict,String[] words,List<String> cur){
//the final size of current formed list should contain
int len = words[0].length();
if(cur.size() == len){
result.add(new ArrayList(cur));
return;
}
//Other wise keep checking
StringBuilder check = new StringBuilder();
for(int i = 0; i < cur.size();i++){
check.append(cur.get(i).charAt(cur.size()));
}
List<String> prefixList = dict.getPrefix(check.toString());
for(String s : prefixList){
cur.add(s);
helper(result,dict,words,cur);
cur.remove(cur.size() - 1);
}
}
}
472. Concatenated Words
对于Trie的用法 也可以不写Trie Class 直接声明建Trie的函数 这里需要判断一个词在不在字典里 所以加了一个hasWord的变量 分别检查每个单词看是不是可以由字典里的单词组成 移动指针 如果当前单词存在 且下一段的String是存在的则返回True
这道题还可以用DP
public class Solution {
class TrieNode{
boolean hasWord;
TrieNode[] children;
public TrieNode(){
this.children = new TrieNode[26];
this.hasWord = false;
}
}
public List<String> findAllConcatenatedWordsInADict(String[] words) {
List<String> result = new ArrayList<String>();
TrieNode root = buildTrie(words);
for(String str : words){
if(str.length() == 0)continue;
if(check(root,str.toCharArray(),0,0)){
result.add(str);
}
}
return result;
}
//Build the Trie from a list of words
public TrieNode buildTrie(String[] s){
TrieNode root = new TrieNode();
for(String str:s){
addWord(root,str);
}
return root;
}
//Add a single word to the Trie
public void addWord(TrieNode root,String s){
TrieNode p = root;
char[] arr = s.toCharArray();
for(int i = 0;i < s.length();i++){
int idx = arr[i] - 'a';
if(p.children[idx] == null){
p.children[idx] = new TrieNode();
}
p = p.children[idx];
}
p.hasWord = true;
}
//return true if the current word's subword could be find in the Trie Dictionary
public boolean check(TrieNode dict,char[] arr,int index,int count){
if(index == arr.length && count > 1)return true;
TrieNode p = dict;
for(int i = index;i < arr.length; i++){
int idx = arr[i] - 'a';
if(p.children[idx] == null){
return false;
}
if(p.children[idx].hasWord){
if(check(dict,arr,i+1,count+1))return true;
}
//Always provide the next step
p = p.children[idx];
}
return false;
}
}
212. Word Search II
Build Trie and DFS from every char and add to the list if it appears in the Trie
不用构建单词 而是在每个结点处存储 / 以及应对重复String 可以利用Trie本身标记呀
public class Solution {
public class TrieNode{
public boolean isWord;
public TrieNode[] child;
public String word;
public TrieNode(){
this.child = new TrieNode[26];
isWord = false;
this.word = null;
}
}
TrieNode root = new TrieNode();
boolean[][] flag;
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<String>();
flag = new boolean[board.length][board[0].length];
//Build Trie Map
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 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;
node.word = word;
}
}
private void search(char[][] board, int i, int j, TrieNode node, List<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(node.word);
node.isWord = false;
}
search(board, i-1, j, node, result);
search(board, i+1, j, node, result);
search(board, i, j-1, node, result);
search(board, i, j+1, node, result);
flag[i][j] = false;
}
}