leetcode 208(trie, 트라이), 648(trie), 676(trie)

208 https://leetcode.com/problems/implement-trie-prefix-tree/

https://qkqhxla1.tistory.com/1081?category=685988 에서 만든 코드를 갖다 쓴다.

class Trie(object):
    def __init__(self):
        self.trie={}

    def insert(self, word):
        trie=self.trie
        for c in word:
            if c not in trie:
                trie[c]={}
            trie=trie[c]
        trie['#']='#'

    def search(self, word):
        stack = deque([[word, self.trie]])
        while stack:
            word, trie = stack.pop()
            if not word:
                if '#' in trie:
                    return True
                continue

            c = word[0]
            if c in trie:
                stack.append([word[1:], trie[c]])
        return False

    def startsWith(self, prefix):
        stack = deque([[prefix, self.trie]])
        while stack:
            word, trie = stack.pop()
            if not word:
                return True

            c = word[0]
            if c in trie:
                stack.append([word[1:], trie[c]])
        return False

648 https://leetcode.com/problems/replace-words/

trie를 만들고 풀어준다.

from collections import deque

class Solution(object):
    def replaceWords(self, wordlist, sentence):
        def make_trie(wordlist):
            trie = {}
            for word in wordlist:
                t = trie
                for w in word:
                    if w not in t:
                        t[w] = {}
                    t = t[w]
                t['#'] = '#'
            return trie
        
        def search(word, trie):
            stack = deque([[word, '', 0, trie]])
            ret_word = ['', 99999]
            while stack:
                word, ret, _len, trie = stack.pop()
                if '#' in trie and _len < ret_word[1]:
                    ret_word = [ret, _len]
                if not word:
                    continue
                if word[0] in trie:
                    stack.append([word[1:], ret + word[0], _len + 1, trie[word[0]]])
            return ret_word[0]
                
        trie = make_trie(wordlist)
        ret = []
        for word in sentence.split():
            result = search(word, trie)
            if result:
                ret.append(result)
            else:
                ret.append(word)
        return ' '.join(ret)

676 https://leetcode.com/problems/implement-magic-dictionary/

이것도 트라이를 만들고 조금씩 변형해서 푼다.

from collections import deque

class MagicDictionary(object):
    def __init__(self):
        self.trie = {}
        
    def buildDict(self, d):
        for word in d:
            t = self.trie
            for w in word:
                if w not in t:
                    t[w] = {}
                t = t[w]
            t['#'] = '#'

    def search(self, word):
        stack = deque([[word, True, self.trie]])  # word, 변형할수 있는지여부, trie
        while stack:
            word, flag, trie = stack.pop()
            if not word:
                if '#' in trie and not flag:
                    return True
                continue
            if word[0] in trie:
                stack.append([word[1:], flag, trie[word[0]]])
            if flag:  # 아직 한개의 단어를 바꿀수 있으면.
                for key in trie:
                    if key != '#' and word[0] != key:
                        stack.append([word[1:], not flag, trie[key]])
        return False