Trie 的考点
- 实现一个 Trie
- 比较 Trie 和 Hash 的优劣
- 字符矩阵类问题使用 Trie 比 Hash 更高效
- hash和trie查找一个单词在不在都是O(L) 但是由于trie用到L次寻址操作 所以比hash慢
Hash vs Trie
- 互相可替代
- Trie 耗费更少的空间 单次查询 Trie 耗费更多的时间 (复杂度相同，Trie 系数大一些)
注意：
- 不要忘记初始化root
思路：
其实就是实现两个操作
- 插入一个单词
- 查找某个单词或前缀是否存在
208 Implement Trie (Prefix Tree)
211 Add and Search Word - Data structure design
*425 Word Squares 从给定字典中 找出能组成对称矩阵的所有组合
*212 Word Search II 在给定字符矩阵中 找所有字典中的词
208 Implement Trie (Prefix Tree)
class Trie {
class TrieNode{
TrieNode[] children;
boolean isWord;
TrieNode(){
children = new TrieNode[26];
isWord = false;
}
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null){
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null){
return false;
}
current = current.children[index];
}
return current.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String word) {
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null){
return false;
}
current = current.children[index];
}
return true;
}
}
211 Add and Search Word - Data structure design
class WordDictionary {
class Node{
Node[] children;
boolean isWord;
Node(){
children = new Node[26];
isWord = false;
}
}
Node root;
/** Initialize your data structure here. */
public WordDictionary() {
root = new Node();
}
/** Adds a word into the data structure. */
public void addWord(String word) {
Node current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null){
current.children[index] = new Node();
}
current = current.children[index];
}
current.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 find(word, 0, root);
}
private boolean find(String word, int index, Node node){
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
if(c=='.'){
for(int j=0; j<26; j++){
if(node.children[j]!=null){
if(find(word, index+1, node.children[j]))
return true;
}
}
return false;
}else{
return node.children[c-'a']!=null && find(word, index+1, node.children[c-'a']);
}
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
425 Word Squares 从给定字典中 找出能组成对称矩阵的所有组合
class Solution {
static class TrieNode{
TrieNode[] children;
boolean isWord;
Set<String> list;
TrieNode(){
children = new TrieNode[26];
isWord = false;
list = new HashSet<>();
}
}
static TrieNode root;
private static void build(String[] words){
for(String s : words){
buildHelper(s);
}
}
private static void buildHelper(String s){
TrieNode current = root;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
int index = c-'a';
if(current.children[index]==null)
current.children[index] = new TrieNode();
current.list.add(s);
current = current.children[index];
}
current.isWord = true;
current.list.add(s);
}
private static Set<String> getWordsWithPrefix(String prefix){
Set<String> result = new HashSet<>();
TrieNode current = root;
for(int i=0; i<prefix.length(); i++){
char c = prefix.charAt(i);
int index = c-'a';
if(current.children[index]==null)
return result;
current = current.children[index];
}
return current.list;
}
public static List<List<String>> wordSquares(String[] words) {
List<List<String>> results = new ArrayList<>();
if(words==null || words.length==0 || words[0].length()==0)
return results;
root = new TrieNode();
build(words);
helper(words, results, new ArrayList<String>());
return results;
}
private static void helper(String[] words, List<List<String>> results, List<String> subset){
int size = words[0].length();
if(subset.size() == size){
results.add(new ArrayList<String>(subset));
return;
}
StringBuilder sb = new StringBuilder();
for(String s : subset){
sb.append(s.charAt(subset.size()));
}
String prefix = sb.toString();
Set<String> set = getWordsWithPrefix(prefix);
for(String s : set){
subset.add(s);
helper(words, results, subset);
subset.remove(subset.size()-1);
}
}
}
212 Word Search II 在给定字符矩阵中 找所有字典中的词
- 用hashmap
class Solution {
public List<String> findWords(char[][] board, String[] words) {
Set<String> prefixs = new HashSet<>();
Set<String> wordSet = new HashSet<>();
for(int j=0; j<words.length; j++){
String word = words[j];
wordSet.add(word);
for(int i=0; i<word.length(); i++){
String prefix = word.substring(0, i+1);
prefixs.add(prefix);
}
}
boolean[][] visited = new boolean[board.length][board[0].length];
Set<String> results = new HashSet<>();
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
visited[i][j] = true;
helper(board, visited, i, j, prefixs, wordSet, results, String.valueOf(board[i][j]));
visited[i][j] = false;
}
}
return new ArrayList<String>(results);
}
private void helper(char[][] board, boolean[][] visited, int x, int y, Set<String> prefixs, Set<String> wordSet, Set<String> results, String temp){
if(wordSet.contains(temp)){
results.add(temp);
}
if(!prefixs.contains(temp))
return;
int[] dirx = {1,-1,0,0};
int[] diry = {0,0,1,-1};
for(int i=0; i<4; i++){
if(isValid(board, x+dirx[i], y+diry[i], visited)){
visited[x+dirx[i]][y+diry[i]] = true;
helper(board, visited, x+dirx[i], y+diry[i], prefixs, wordSet, results, temp+board[x+dirx[i]][y+diry[i]]);
visited[x+dirx[i]][y+diry[i]] = false;
}
}
}
private boolean isValid(char[][] board,int x, int y, boolean[][] visited){
if(x>=0 && x<board.length && y>=0 && y<board[0].length && visited[x][y]==false)
return true;
return false;
}
}
- 用trie
class Solution {
static class TrieNode{
TrieNode[] children;
TrieNode(){
children = new TrieNode[26];
}
}
static TrieNode root;
private static void build(String[] words){
for(String word: words){
builderHelper(word);
}
}
private static void builderHelper(String word){
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current.children[index]==null)
current.children[index] = new TrieNode();
current = current.children[index];
}
}
private static boolean startWith(String word){
TrieNode current = root;
for(char c : word.toCharArray()){
int index = c - 'a';
if(current==null || current.children[index]==null)
return false;
current = current.children[index];
}
return true;
}
public static List<String> findWords(char[][] board, String[] words) {
Set<String> results = new HashSet<>();
root = new TrieNode();
build(words);
Set<String> set = new HashSet<>();
for(String s: words){
set.add(s);
}
boolean[][] visited = new boolean[board.length][board[0].length];
for(int i=0; i<board.length; i++){
for(int j=0; j<board[0].length; j++){
StringBuilder sb = new StringBuilder();
sb.append(board[i][j]);
visited[i][j] = true;
helper(i, j, board, set, results, sb, visited);
visited[i][j] = false;
}
}
List<String> solutions = new ArrayList<>();
for(String s: results){
solutions.add(s);
}
return solutions;
}
private static void helper(int row, int col, char[][] board, Set<String> set, Set<String> results, StringBuilder sb, boolean[][] visited){
if(set.contains(sb.toString()))
results.add(sb.toString());
int[] dirx = {1, -1, 0, 0};
int[] diry = {0, 0, -1, 1};
for(int i=0; i<4; i++){
int x = row + dirx[i];
int y = col + diry[i];
if(!valid(x, y, visited)){
continue;
}
sb.append(board[x][y]);
if(!startWith(sb.toString())){
sb.deleteCharAt(sb.length()-1);
continue;
}
visited[x][y] = true;
helper(x, y, board, set, results, sb, visited);
sb.deleteCharAt(sb.length()-1);
visited[x][y] = false;
}
}
private static boolean valid(int x, int y, boolean[][] visited){
return x>=0 && x<visited.length && y>=0 && y<visited[0].length && !visited[x][y];
}
}
