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

資訊專欄INFORMATION COLUMN

leetcode-211-Add and Search Word - Data structure

Alliot / 2627人閱讀

摘要:原題總結棧的利用,先進后出的作用,可以保持鏈表一類的數據的連貫操作,可以用來替代廣度搜索。每一層次可以用進棧出棧進行替代。形式的數據結構,有記憶狀態的作用。應用字符串的遍歷,廣度搜索。

原題:
211. Add and Search Word - Data structure design

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.
總結:棧 stack 的利用,先進后出的作用,可以保持 鏈表一類的數據的連貫操作,可以用來替代廣度搜索。
每一層次可以用進棧出棧進行替代。
stack=[(node,str)],形式的數據結構,有記憶狀態的作用。
應用: 字符串的遍歷,廣度搜索。
    
import collections

class WordNode:
    def __init__(self):
        self.children = {}
        self.isEnd = False

class WordDictionary:
    def __init__(self):
        self.root = WordNode()

    def addWord(self, word):
        cur_node=self.root
        for char_iter in word:
            if char_iter in cur_node.children:
                cur_node=cur_node.children[char_iter]
            else:
                new_node=WordNode()
                cur_node.children[char_iter]=new_node
                cur_node=new_node
            # cur_node=cur_node.children[char_iter]
        cur_node.isEnd=True

    def search(self, word):
        stack=[(self.root,word)]
        while stack:
            node,w=stack.pop()
            if not w:
                if node.isEnd:
                    return True
            # print([w])
            elif w[0] == ".":
                for node_iter in node.children.values():
                    stack.append((node_iter,w[1:]))
            elif w[0] in node.children:
                nodes_cur=node.children[w[0]]
                stack.append((nodes_cur,w[1:]))
            else:
                pass
        return False




class WordDictionary:
    def __init__(self):
        self.root = WordNode()

    def addWord(self, word):
        node = self.root
        for w in word:
            if w in node.children:
                node = node.children[w]
            else:
                node.children[w] = WordNode()
                node = node.children[w]
        node.isEnd = True

    def search(self, word):
        stack = [(self.root, word)]
        while stack:
            node, w = stack.pop()
            if not w:
                if node.isEnd:
                    return True
            elif w[0] == ".":
                for n in node.children.values():
                    stack.append((n, w[1:]))
            else:
                if w[0] in node.children:
                    n = node.children[w[0]]
                    stack.append((n, w[1:]))
        return False


if __name__=="__main__":
    wd=WordDictionary()
    # wd.addWord("bad")
    # wd.addWord("dad")
    # wd.addWord("mad")
    # out=wd.search("pad")
    # print(out)
    # out =wd.search("bad")
    # print(out)
    # out =wd.search(".ad")
    # print(out)
    # out =wd.search("b..")
    # print(out)

    words=["WordDictionary", "addWord", "addWord", "search", "search", "search", "search", "search", "search"]
    detect_words=[ ["a"], ["a"], ["."], ["a"], ["aa"], ["a"], [".a"], ["a."]]
    for word in words:
        wd.addWord(word)
    for detect_word in detect_words:
        out=wd.search(detect_word[0])
        print(out)

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/42286.html

相關文章

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

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

    mozillazg 評論0 收藏0
  • [Leetcode] Implement Trie 實現前綴樹

    摘要:壓縮前綴樹其實就是將所有只有一個子節點的節點合并成一個,以減少沒有意義的類似鏈表式的鏈接。然后我們開始遍歷這個前綴樹。 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
  • [LintCode] Implement Trie

    Problem Implement a trie with insert, search, and startsWith methods. Example insert(lintcode) search(code) // return false startsWith(lint) // return true startsWith(linterror) // return false insert...

    chengjianhua 評論0 收藏0
  • [LintCode/LeetCode] Implement Trie

    摘要:首先,我們應該了解字典樹的性質和結構,就會很容易實現要求的三個相似的功能插入,查找,前綴查找。既然叫做字典樹,它一定具有順序存放個字母的性質。所以,在字典樹的里面,添加,和三個參數。 Problem Implement a trie with insert, search, and startsWith methods. Notice You may assume that all i...

    付永剛 評論0 收藏0

發表評論

0條評論

Alliot

|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<