[Leetcode] 0208. Trie 구현

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

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

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

Trie 클래스를 구현합니다.

  • 트라이() 트라이 객체를 초기화합니다.
  • void insert(문자열 단어) 문자열을 삽입합니다 단어 트리에 들어가다.
  • boolean 검색(문자열 단어) 보고 진실 만약 문자열이라면 단어 트라이에 있음(즉, 이전에 삽입됨) 거짓 그렇지 않으면.
  • boolean startsWith(문자열 접두사) 보고 진실 이전에 삽입된 문자열이 있는 경우 단어 접두사가 붙은 것 접두사, 그리고 거짓 그렇지 않으면.

 

예시 1:

입력
["Trie", "삽입", "검색", "검색", "startsWith", "삽입", "검색"] [[], ["apple"], ["apple"], ["앱"], ["앱"], ["앱"], ["앱"]]
산출
[null, null, true, false, true, null, true]

설명
트라이 트라이 = 새로운 트라이(); trie.insert("사과"); trie.search("사과"); // True를 반환합니다 trie.search("app"); // False를 반환합니다 trie.startsWith("app"); // True를 반환합니다 trie.insert("app"); trie.search("앱"); // True를 반환합니다.

 

제약:

  • 1 <= 단어 길이, 접두사 길이 <= 2000
  • 단어 그리고 접두사 소문자 영어 글자로만 구성됩니다.
  • 최대 3 * 10 4 전화하다 총체적으로 만들어질 것이다 끼워 넣다, 찾다, 그리고 시작으로.

파이썬

				
					# insert() # 시간 복잡도: O(l) # 공간 복잡도: O(l) # search() # 시간 복잡도: O(l) # 공간 복잡도: O(1) # search prefix() # 시간 복잡도: O(l) # 공간 복잡도: O(1) 클래스 TrieNode: def __init__(self, char: str = ""): self.char = char self.children = {} self.isEnd = False 클래스 Trie: def __init__(self): self.root = TrieNode() def insert(self, word: str): node = self.root for c in word: if c in node.children: node = node.children[c] else: newNode = TrieNode() node.children[c] = newNode node = newNode node.isEnd = True def search(self, word: str): node = self.root for c in 단어: if c not in node.children: return False node = node.children[c] return node.isEnd def startsWith(self, prefix: str): node = self.root for c in prefix: if c not in node.children: return False node = node.children[c] return True # 귀하의 Trie 객체는 다음과 같이 인스턴스화되고 호출됩니다. trie = Trie() trie.insert("apple") print(trie.search("apple")) print(trie.search("app")) print(trie.startsWith("app")) trie.insert("app") print(trie.search("app"))

관련 기사