亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

mozillazg / 1227人閱讀

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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/71804.html

相關(guān)文章

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

    摘要：原題總結(jié)棧的利用，先進(jìn)后出的作用，可以保持鏈表一類的數(shù)據(jù)的連貫操作，可以用來(lái)替代廣度搜索。每一層次可以用進(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 評(píng)論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 評(píng)論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 評(píng)論0 收藏0

  • [Leetcode] Word Search 單詞搜索

    摘要：我們可以先用待查單詞建立一個(gè)字典樹(shù)，這樣我們?cè)趶木仃囍心硞€(gè)點(diǎn)開(kāi)始深度優(yōu)先搜索時(shí)，可以直接用字典樹(shù)判斷當(dāng)前組成的字符串是否是某個(gè)單詞的前綴。字典樹(shù)同樣也提供接口，所以同樣可以用于判斷是否已經(jīng)搜索到這個(gè)詞了。 Word Search I 更新的思路與解法請(qǐng)?jiān)L問(wèn)：https://yanjia.me/zh/2018/11/... Given a 2D board and a word, f...

    objc94 評(píng)論0 收藏0

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

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

    jsliang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<