[Leetcode] 1804. Trie II 구현

/ 리트코드, 기술 기사 / 에 의해

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 4 전화하다 총체적으로 만들어질 것이다 끼워 넣다, 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"))

관련 기사