国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[LeetCode] 211. Add and Search Word - Data structu

mozillazg / 1166人閱讀

Problem

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 letters a-z or .. A . means it can represent any one letter.

Example:

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
Note:
You may assume that all words are consist of lowercase letters a-z.

Solution 
class WordDictionary {
    public class TrieNode {
        public TrieNode[] children = new TrieNode[26];
        public boolean isWord = false;
    }
    
    TrieNode root = new TrieNode();
    
    public void addWord(String word) {
        TrieNode node = root;
        for (char ch: word.toCharArray()) {
            if (node.children[ch-"a"] == null) {
                node.children[ch-"a"] = new TrieNode();
            }
            node = node.children[ch-"a"];
        }
        node.isWord = true;
    }

    public boolean search(String word) {
        return helper(word, 0, root);
    }
    
    private boolean helper(String word, int start, TrieNode node) {
        if (start == word.length()) return node.isWord;
        char ch = word.charAt(start);
        if (ch == ".") {
            for (int i = 0; i < 26; i++) {
                if (node.children[i] != null && helper(word, start+1, node.children[i])) {
                    return true;
                }
            }
        } else {
            return node.children[ch-"a"] != null && helper(word, start+1, node.children[ch-"a"]);
        }
        return false;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71804.html

相關(guān)文章

  • leetcode-211-Add and Search Word - Data structure

    摘要：原題總結(jié)棧的利用，先進(jìn)后出的作用，可以保持鏈表一類的數(shù)據(jù)的連貫操作，可以用來替代廣度搜索。每一層次可以用進(jìn)棧出棧進(jìn)行替代。形式的數(shù)據(jù)結(jié)構(gòu)，有記憶狀態(tài)的作用。應(yīng)用字符串的遍歷，廣度搜索。 原題： 211. Add and Search Word - Data structure design Design a data structure that supports the follo...

    Alliot 評論0 收藏0

  • [LeetCode] 642. Design Search Autocomplete System

    Problem Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character #). For each character they type except #, you need to r...

    MartinHan 評論0 收藏0

  • [LeetCode] 212. Word Search II

    Problem 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 ...

    Flands 評論0 收藏0

  • [Leetcode] Word Search 單詞搜索

    摘要：我們可以先用待查單詞建立一個字典樹，這樣我們在從矩陣中某個點(diǎn)開始深度優(yōu)先搜索時，可以直接用字典樹判斷當(dāng)前組成的字符串是否是某個單詞的前綴。字典樹同樣也提供接口，所以同樣可以用于判斷是否已經(jīng)搜索到這個詞了。 Word Search I 更新的思路與解法請訪問：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

    objc94 評論0 收藏0

  • [Leetcode] Implement Trie 實(shí)現(xiàn)前綴樹

    摘要：壓縮前綴樹其實(shí)就是將所有只有一個子節(jié)點(diǎn)的節(jié)點(diǎn)合并成一個，以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 Implement Trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowe...

    jsliang 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<