python-计算前面出现的单词数

2021-01-03 20点热度 0人点赞 0条评论

我想问一下,我们如何计算在trie中给定字符串之前按字母顺序出现的单词数?

下面是我的实现。

class TrieNode:
    # Trie node class
    def __init__(self):
        self.children = [None] * 26
        # isEndOfWord is True if node represent the end of the word
        self.isEndOfWord = False
        self.word_count = 0
class Trie:
    # Trie data structure class
    def __init__(self):
        self.root = self.getNode()

    def getNode(self):
        # Returns new trie node (initialized to NULLs)
        return TrieNode()

    def _charToIndex(self, ch):
        # private helper function
        # Converts key current character into index
        # use only 'a' through 'z' and lower case
        return ord(ch) - ord('a')

    def insert(self, key):
        # If not present, inserts key into trie
        # If the key is prefix of trie node,
        # just marks leaf node
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            # if current character is not present
            if not pCrawl.children[index]:
                pCrawl.children[index] = self.getNode()
            pCrawl = pCrawl.children[index]
            # mark last node as leaf
        pCrawl.isEndOfWord = True
        pCrawl.word_count += 1

    def search(self, key):
        # Search key in the trie
        # Returns true if key presents
        # in trie, else false
        pCrawl = self.root
        length = len(key)
        for level in range(length):
            index = self._charToIndex(key[level])
            if not pCrawl.children[index]:
                return False
            pCrawl = pCrawl.children[index]
        return pCrawl is not None and pCrawl.isEndOfWord

    def count_before(self, string):
        cur = self.root
        for b in string:
            index = self._charToIndex(b)
            print(index)
            cur = cur.children[index]
            if cur is None:
                return 0
        return cur.word_count
def total_before(text):
    t = Trie()
    for i in range(len(text)):
        t.insert(text[i])
    
    a_list = [] # A list to store the result that occur before the text[i]
    for i in range(len(text)):
        result = t.count_before(text[i])
        a_list.append(result)
    return a_list

total_before(["bac", "aaa", "baa", "aac"]) # Output will be [3, 0, 2, 1]

我想知道如何计算在我创建的trie中给定字符串之前出现的单词数。有人能给我个主意吗?

查看隐藏内容需要支付:¥1
查看

未经允许不得转载!python-计算前面出现的单词数

本文地址:https://ans.52learn.online/1882

ANS52LEARN

DO BEST