การค้นหาคำนำหน้าและ Starts-With

พลังของการสืบค้นคำนำหน้า

เมธอด starts_with

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True

t = Trie()
for w in ['hello','help','world','word']:
    t.insert(w)
print(t.starts_with('hel'))   # True
print(t.starts_with('wor'))   # True
print(t.starts_with('xyz'))   # False

Autocomplete: การค้นหาคำทั้งหมดที่มีคำนำหน้า

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def autocomplete(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return []
            node = node.children[c]
        # DFS from prefix end node
        results = []
        def dfs(n, path):
            if n.is_end:
                results.append(prefix + path)
            for char, child in n.children.items():
                dfs(child, path + char)
        dfs(node, '')
        return results

t = Trie()
for w in ['apple','app','application','apply','apt']:
    t.insert(w)
print(t.autocomplete('app'))  # ['app','apple','apply','application']

การส่งคืนคำแนะนำที่เรียงลำดับแล้ว

def dfs_sorted(node, prefix, results):
    if node.is_end:
        results.append(prefix)
    for char in sorted(node.children.keys()):  # alphabetical order
        dfs_sorted(node.children[char], prefix + char, results)

print('Iterating children in sorted order gives lex-sorted suggestions')

คำแนะนำ autocomplete อันดับต้น ๆ จำนวน k รายการ

การใช้งาน Trie สำหรับ LeetCode 208

class Trie:
    def __init__(self):
        self.root = {}
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['#'] = True  # '#' marks word end
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node: return False
            node = node[c]
        return '#' in node
    
    def startsWith(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node: return False
            node = node[c]
        return True

t = Trie()
t.insert('apple')
print(t.search('apple'))      # True
print(t.search('app'))        # False
print(t.startsWith('app'))   # True

การใช้ '#' เป็นเครื่องหมายจุดสิ้นสุด (Trie แบบพจนานุกรม)

การหาคำนำหน้าร่วมที่ยาวที่สุดด้วย Trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def longest_common_prefix(words):
    root = TrieNode()
    for word in words:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    prefix = []
    node = root
    while len(node.children) == 1 and not node.is_end:
        char, node = next(iter(node.children.items()))
        prefix.append(char)
    return ''.join(prefix)

print(longest_common_prefix(['flower','flow','flight']))  # 'fl'
print(longest_common_prefix(['dog','racecar','car']))     # ''

ปัญหาการแทนที่คำ

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def replaceWords(dictionary, sentence):
    root = TrieNode()
    for word in dictionary:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def find_root(word):
        node = root
        for i, c in enumerate(word):
            if c not in node.children: break
            node = node.children[c]
            if node.is_end:
                return word[:i+1]
        return word
    
    return ' '.join(find_root(w) for w in sentence.split())

print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))

ปัญหาคู่ผลรวมจากแผนที่

การนำการเติมคำอัตโนมัติที่มีผลลัพธ์จำกัดไปใช้งาน

ตรวจสอบความเข้าใจอย่างรวดเร็ว

สรุปบทเรียน