Design Add and Search Words Data Structure

Q: 단어 추가 및 검색의 시간 복잡도는 얼마인가요?

길이가 L 인 단어를 추가하는 데는 O(L) 이 걸리며, 저장된 단어 수와 관계없이 점이 없는 검색에도 같은 시간이 걸립니다. d 개의 점이 있는 검색은 최악의 경우 O(26^d · L) 이 걸립니다. 메모리는 추가된 글자 T 개에 대해 O(T) 개의 노드를 사용합니다.

보통트라이 백트래킹

+10

두 가지 연산을 지원하는 단어 사전을 만드세요. addWord w는 단어 w를 저장합니다. search p는 저장된 단어 중 패턴 p와 일치하는 단어가 있는지 알려 줍니다. 길이가 같고, 각 위치에서 패턴이 같은 문자이거나 임의의 문자 하나를 나타내는 점 .이어야 합니다.

연산 i는 단어 또는 패턴 words[i]에 대한 ops[i]입니다. 빈 사전에서 연산을 순서대로 실행하고 각각에 대해 문자열 하나를 반환하세요. addWord에는 "null"을, search에는 "true" 또는 "false"를 반환합니다.

함수

wordDictionaryOps(ops: string-array, words: string-array) → string-array

opsstring-array: 연산, 실행되는 순서대로
wordsstring-array: 추가할 단어 또는 검색할 패턴(작업당 하나)
반환값string-array: 연산마다 텍스트로 답 하나씩

제약 조건

1 ≤ ops.length ≤ 2500
words.length == ops.length
모든 ops[i]는 addWord 또는 search입니다.
1 ≤ words[i].length ≤ 20
추가할 단어에는 소문자 영어 알파벳만 포함됩니다.
검색 패턴에는 소문자 영어 알파벳과 점이 최대 3개 포함됩니다.

예제

입력: ops = ["addWord", "addWord", "search", "search", "search", "search"]words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]
출력: ["null", "null", "true", "false", "false", "true"]
설명: r.se는 두 단어 모두와 일치합니다. 점은 rose의 o와 rise의 i를 나타냅니다. 점은 빠진 글자를 나타내지 않으므로 ros와 rose.는 일치하지 않습니다. 두 단어 모두 세 번째 글자가 s이므로 ..s.는 일치합니다.

입력: ops = ["search", "addWord", "search", "search", "search"]words = ["...", "sky", "...", "s.y", "sk"]
출력: ["false", "null", "true", "true", "false"]
설명: 딕셔너리는 비어 있는 상태로 시작하므로 ...는 아무것도 찾지 못합니다. sky를 추가하면 ...와 s.y는 모두 일치하지만, sk는 너무 짧습니다.

입력: ops = ["addWord", "addWord", "search", "search", "search"]words = ["maple", "mango", "ma..o", "m...y", "m.p.e"]
출력: ["null", "null", "true", "false", "true"]
설명: ma..o의 첫 번째 점은 maple의 p이거나 mango의 n일 수 있습니다. maple은 e로 끝나지만 mango는 조건에 맞습니다. y로 끝나는 단어는 없으므로 m...y는 실패하고, m.p.e는 maple과 일치합니다.

후속 질문

패턴에 빈 문자열을 포함해 임의 개수의 문자를 나타내는 *도 포함될 수 있다면, search를 어떻게 확장하시겠습니까?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

점은 검색에서 원하는 단어를 지정할 수 없다는 뜻입니다. ma..o는 676개의 가능한 단어를 나타내며, 저장된 단어만 중요합니다. 트라이에서는 같은 글자로 시작하는 단어들이 하나의 경로를 공유합니다. 패턴의 문자는 링크 하나를 따라가고, 점은 존재하는 자식 노드로만 갈라지며, 깊이 우선 검색은 막다른 분기에서 되돌아옵니다.

패턴을 저장된 모든 단어와 비교합니다

핵심 아이디어

추가된 단어를 목록에 보관하고 각 단어를 패턴과 대조해 보세요. 길이가 같고, 모든 위치에서 마침표가 있거나 같은 글자가 있으면 일치하는 것입니다. 저장된 모든 단어와 대조해 확인하므로 정답입니다.

검색할 때마다 목록 전체를 확인해야 하므로, 최대 L개의 글자로 이루어진 단어 n개가 있다면 점이 하나도 없는 패턴이라도 O(n·L)의 비용이 듭니다. 1,250번 추가한 다음 1,250번 검색하면 단어를 1,250 × 1,250 = 1,562,500개 확인하게 됩니다.

알고리즘

추가된 단어를 목록에 보관하세요. addWord w의 경우 w를 추가하고 "null"을 기록하세요.
search p의 경우 p를 같은 길이의 각 단어와 위치별로 비교하고, 점은 어떤 문자든 허용하도록 하세요.
첫 번째로 일치하는 항목에서 "true"를 기록하고, 일치하는 항목이 없으면 "false"를 기록하세요.

def matches(pattern, word):
    # Same length, and every position holds a dot or the same letter.
    if len(pattern) != len(word):
        return False
    for p, w in zip(pattern, word):
        if p != "." and p != w:
            return False
    return True


def wordDictionaryOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            stored.append(word)
            result.append("null")
        else:
            found = any(matches(word, s) for s in stored)
            result.append("true" if found else "false")
    return result

점에서 깊이 우선 탐색을 하는 트라이

핵심 아이디어

단어를 트라이에 넣습니다. rose와 rise는 r 노드를 공유한 다음 o와 i로 갈라집니다. 종료 플래그는 저장된 단어가 끝나는 각 노드를 표시합니다. 문자 패턴은 트라이를 따라 내려가는 한 번의 탐색입니다. 점은 어떤 문자든 될 수 있으므로, 점에서는 기존 자식을 모두 시도하고 그중 하나가 일치하는 경로로 이어지는 즉시 true를 반환합니다.

ma..o의 경우 ma 노드에는 p와 n 자식이 있습니다. p를 거치면 두 번째 점에서 l에 도달하는데, l에는 o 자식이 없으므로 탐색은 되돌아가 n을 시도합니다. 그러면 g, 이어서 o에 도달하고, 여기서 mango가 끝납니다.

일치하려면 플래그가 설정된 노드에서 패턴 전체를 소진해야 하므로 길이 조건도 해결됩니다. ros는 플래그가 설정되지 않은 노드에서 멈추고, rose.는 이어지는 링크가 없어 진행이 끝납니다. 점 하나는 최대 26개의 분기를 열 수 있으므로 점이 d개인 경우 방문하는 노드는 최대 26^d · L개이며, 점이 없는 패턴의 비용은 O(L)입니다.

알고리즘

각 노드에는 자식 링크와 처음에는 꺼져 있는 끝 표시가 있습니다.
addWord w의 경우: 루트에서 시작해 w를 따라 내려가며, 없는 노드를 만들고, 이동이 멈춘 곳의 끝 표시를 설정합니다.
match(node, i): i가 패턴의 길이와 같으면 노드의 끝 표시를 반환합니다.
p[i]가 문자라면 자식이 없을 경우 false를 반환하고, 그렇지 않으면 match(child, i+1)을 반환합니다. 점이라면 기존 자식 중 하나에 대해 match(child, i+1)이 성공할 경우 true를 반환하고, 그렇지 않으면 false를 반환합니다.
검색할 때마다 match(root, 0)을 기록하고, 추가할 때마다 "null"을 기록합니다.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


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

    def add_word(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, pattern):
        return self._match(self.root, pattern, 0)

    def _match(self, node, pattern, i):
        # Can the path below node spell pattern[i:] and end on a stored word?
        if i == len(pattern):
            return node.is_end
        ch = pattern[i]
        if ch == ".":
            # A dot stands for any letter: try each child until one works.
            for child in node.children.values():
                if self._match(child, pattern, i + 1):
                    return True
            return False
        child = node.children.get(ch)
        return child is not None and self._match(child, pattern, i + 1)


def wordDictionaryOps(ops, words):
    dictionary = WordDictionary()
    result = []
    for op, word in zip(ops, words):
        if op == "addWord":
            dictionary.add_word(word)
            result.append("null")
        else:
            result.append("true" if dictionary.search(word) else "false")
    return result

함정과 경계 사례

첫 번째 자식이 점의 일치 여부를 결정하게 하는 것. ma..o에서 p 분기는 실패하고 n 분기는 성공하므로, 첫 번째 자식의 결과를 반환하는 코드는 p를 먼저 시도할 때 false라고 답합니다. 모든 자식이 실패한 뒤에만 false라고 답하세요.
어떤 노드에서든 패턴이 끝나면 true라고 답하는 것. rose를 추가한 뒤 ros는 노드에 도달하지만, 그 지점에서 끝나는 단어는 없습니다. 끝 플래그를 확인하세요.
점이 없는 글자와 일치하게 하는 것. card.는 cards와 일치하지만 card와는 일치하지 않습니다.
점을 문자로 취급하는 것. 26칸 배열에서 '.' - 'a'로 인덱싱하면 배열 범위 밖을 읽게 되므로, 먼저 점인지 확인하세요.

자주 묻는 질문3

단어 추가 및 검색의 시간 복잡도는 얼마인가요?

길이가 L인 단어를 추가하는 데는 O(L)이 걸리며, 저장된 단어 수와 관계없이 점이 없는 검색에도 같은 시간이 걸립니다. d개의 점이 있는 검색은 최악의 경우 O(26^d · L)이 걸립니다. 메모리는 추가된 글자 T개에 대해 O(T)개의 노드를 사용합니다.

트라이 대신 해시 집합으로 풀 수 있나요?

네, 다만 장단점이 있습니다. 집합은 점이 없는 패턴에 대해 한 번의 조회로 답을 찾습니다. 점이 있으면 저장된 모든 단어 중 해당 길이의 단어를 하나씩 확인하거나(O(n·L)), 각 점을 26개의 모든 문자로 채우고 결과를 각각 조회해야 합니다. 점이 세 개라면 17,576번 조회합니다.

트라이 검색은 재귀적으로 해야 할까요, 반복적으로 해야 할까요?

둘 다 괜찮습니다. 재귀는 패턴의 각 문자마다 한 단계씩 진행되며, 여기서는 최대 20단계이므로 호출 스택이 작게 유지됩니다. 반복 버전은 (node, position) 쌍의 스택을 유지하고 점을 만나면 모든 자식을 스택에 넣습니다.

def wordDictionaryOps(ops, words):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

ops = ["addWord", "addWord", "search", "search", "search", "search"]
words = ["rose", "rise", "r.se", "ros", "rose.", "..s."]

예상 출력

["null", "null", "true", "false", "false", "true"]