強化二 字典樹 Trie

Trie 的考點

  • 實現(xiàn)一個 Trie
  • 比較 Trie 和 Hash 的優(yōu)劣
  • 字符矩陣類問題使用 Trie 比 Hash 更高效
  • hash和trie查找一個單詞在不在都是O(L) 但是由于trie用到L次尋址操作 所以比hash慢

Hash vs Trie

  • 互相可替代
  • Trie 耗費更少的空間 單次查詢 Trie 耗費更多的時間 (復(fù)雜度相同，Trie 系數(shù)大一些)

注意：

  • 不要忘記初始化root

思路：
其實就是實現(xiàn)兩個操作

  • 插入一個單詞
  • 查找某個單詞或前綴是否存在

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];
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗。 張土汪：刷leetcod...
    土汪閱讀 12,916評論 0贊 33
  • 算法思想貪心思想雙指針排序快速選擇堆排序桶排序荷蘭國旗問題二分查找搜索BFSDFSBacktracking分治動態(tài)...
    第六象限閱讀 4,902評論 0贊 0
  • LeetCode 刷題隨手記 - 第一部分 前 256 題（非會員），僅算法題，的吐槽 https://leetc...
    蕾娜漢默閱讀 18,388評論 2贊 36
  • 《擺渡人1》給我們講述了少女迪倫遭遇車禍喪生，由擺渡人崔斯坦引領(lǐng)走出荒原去往另一個世界，但最后為了愛，他們越過重重...
    _桃李不言_閱讀 1,125評論 0贊 1
  • 一整天的訂貨，很是燒腦！經(jīng)過跟工廠的溝通，我們明確了幾點：老板要明確自己的目標(biāo)。要帶領(lǐng)團隊一起打造目標(biāo)市場。窮日子...
    TA77范麗萍閱讀 181評論 0贊 0

友情鏈接更多精彩內(nèi)容