[Leetcode] 1804. Trie II 구현

2025년 3월 28일 / 리트코드, 기술 기사 / 에 의해 록산

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

목차

중간

에이 트리 (발음은 "try" 또는 접두사 트리 문자열 데이터 세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다. 이 데이터 구조는 자동완성이나 맞춤법 검사기 등 다양한 용도로 사용됩니다.

Trie 클래스를 구현합니다.

트라이() 트라이 객체를 초기화합니다.
void insert(문자열 단어) 문자열을 삽입합니다 단어 트리에 들어가다.
int countWordsEqualTo(문자열 단어) 문자열의 인스턴스 수를 반환합니다. 단어 트리에서.
int countWordsStartingWith(문자열 접두사) 문자열이 포함된 트라이의 문자열 수를 반환합니다. 접두사 접두사로.
void erase(문자열 단어) 문자열을 지웁니다 단어 트리에서.

예시 1:

입력
["Trie", "삽입", "삽입", "단어 수와 같음", "시작 단어 수와 같음", "지우기", "단어 수와 같음", "시작 단어 수와 같음", "지우기", "시작 단어 수와 같음"] [[], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"], ["apple"], ["app"]]
산출
[널, 널, 널, 2, 2, 널, 1, 1, 널, 0]

설명
트라이 트라이 = 새로운 트라이(); trie.insert("사과"); // "apple"을 삽입합니다. trie.insert("사과"); // 다른 "사과"를 삽입합니다. trie.countWordsEqualTo("사과"); // "apple"이 두 개 있으므로 2를 반환합니다. trie.countWordsStartingWith("app"); // "app"은 "apple"의 접두사이므로 2를 반환합니다. trie.erase("apple"); // "사과" 하나를 지웁니다. trie.countWordsEqualTo("사과"); // 이제 "apple"의 인스턴스가 하나만 있으므로 1을 반환합니다. trie.countWordsStartingWith("app"); // 1 trie.erase("apple");를 반환합니다. // "apple"을 지웁니다. 이제 트리는 비어있습니다. trie.countWordsStartingWith("앱"); // 0을 반환합니다.

제약:

1 <= 단어 길이, 접두사 길이 <= 2000
단어 그리고 접두사 소문자 영어 글자로만 구성됩니다.
최대 3 * 10 ⁴ 전화하다 총체적으로 만들어질 것이다 끼워 넣다, countWordsEqualTo, countWords시작 단어, 그리고 지우다.
모든 함수 호출에 대해 보장됩니다. 지우다, 문자열 단어 트리에 존재할 것이다.

파이썬

				
					클래스 TrieNode: def __init__(self): self.links = [None] * 26 self.wordsEndingHere = 0 self.wordsStartingHere = 0 클래스 Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: node = self.root w in word: charIndex = ord(w) - ord('a') node.links[charIndex]가 아니면: node.links[charIndex] = TrieNode() node = node.links[charIndex] node.wordsStartingHere += 1 node.wordsEndingHere += 1 def countWordsEqualTo(self, word: str) -> int: node = self.root w in word: charIndex = ord(w) - ord('a') node.links[charIndex]가 아니면: return 0 node = node.links[charIndex] return node.wordsEndingHere def countWordsStartingWith(self, prefix: str) -> int: node = self.root for w in prefix: charIndex = ord(w) - ord('a') if not node.links[charIndex]: return 0 node = node.links[charIndex] return node.wordsStartingHere def erase(self, word: str) -> None: node = self.root for w in word: charIndex = ord(w) - ord('a') node = node.links[charIndex] node.wordsStartingHere -= 1 node.wordsEndingHere -= 1 # 귀하의 Trie 객체는 인스턴스화되고 다음과 같이 호출됩니다. trie = Trie() trie.insert("apple") trie.insert("apple") print(trie.countWordsEqualTo("apple")) print(trie.countWordsStartingWith("app")) trie.erase("apple") print(trie.countWordsEqualTo("apple")) print(trie.countWordsStartingWith("app")) trie.erase("apple") print(trie.countWordsStartingWith("app"))

한국어