[Leetcode] 0211. 추가 및 검색어 데이터 구조 설계

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

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

중간

새로운 단어를 추가하고 문자열이 이전에 추가된 문자열과 일치하는지 확인하는 데이터 구조를 설계합니다.

구현하다 단어사전 수업:

  • 단어사전() 객체를 초기화합니다.
  • void addWord(단어) 추가합니다 단어 데이터 구조에 맞게 조정하면 나중에 다시 적용할 수 있습니다.
  • bool 검색(단어) 보고 진실 데이터 구조에 일치하는 문자열이 있는 경우 단어 또는 거짓 그렇지 않으면. 단어 점이 포함될 수 있습니다 '.' 점은 모든 문자와 일치할 수 있습니다.

 

예:

입력
["단어사전","addWord","addWord","addWord","검색","검색","검색","검색"] [[],["나쁨"],["아빠"],["미친"],["패드"],["나쁨"],[".광고"],["b.."]]
산출
[null, null, null, null, false, true, true, true]

설명
단어사전 단어사전 = 새로운 단어사전(); wordDictionary.addWord("잘못된 단어"); wordDictionary.addWord("아빠"); wordDictionary.addWord("mad"); wordDictionary.search("패드"); // False를 반환합니다 wordDictionary.search("bad"); // True를 반환합니다 wordDictionary.search(".ad"); // True를 반환합니다 wordDictionary.search("b.."); // True를 반환합니다.

 

제약:

  • 1 <= 단어 길이 <= 25
  • 단어 ~에 단어 추가 소문자 영어 글자로 구성됩니다.
  • 단어 ~에 찾다 ~로 구성되다 '.' 또는 소문자 영어 글자.
  • 최대가 있을 것입니다 2 점들 단어 ~을 위한 찾다 쿼리.
  • 최대 10 4 전화는 에게 걸릴 것이다 단어 추가 그리고 찾다.

파이썬

				
					# 시간 복잡도: O(M) # 공간 복잡도: O(M) 클래스 TrieNode: def __init__(self): self.children = {} self.isEnd = False 클래스 WordDictionary: def __init__(self): self.root = TrieNode() self.maxLen = 0 def addWord(self, word: str) -> None: node = self.root l = 0 for char in word: if char not in node.children: node.children[char] = TrieNode() node = node.children[char] l += 1 self.maxLen = max(self.maxLen, l) node.isEnd = True def search(self, word: str) -> bool: if len(word) > self.maxLen: return False def helper(idx, node): for i in range(idx, len(word)): if word[i] == ".": for child in node.children.values(): if helper(i + 1, child): True를 반환합니다. False를 반환합니다. 그렇지 않은 경우: word[i]가 node.children에 없는 경우: False를 반환합니다. node = node.children[word[i]]를 반환합니다. node.isEnd를 반환합니다. helper(0, self.root) wordDictionary = WordDictionary() wordDictionary.addWord("bad") wordDictionary.addWord("dad") wordDictionary.addWord("mad") wordDictionary.search("pad")를 인쇄합니다. wordDictionary.search("bad")) wordDictionary.search(".ad")) wordDictionary.search("b.."))를 인쇄합니다.

관련 기사