[LeetCode] 211. Design Add and Search Words Data Structure (C++)

문제

https://leetcode.com/problems/design-add-and-search-words-data-structure/

Design Add and Search Words Data Structure - LeetCode

 

 

풀이

 

난이도: Medium 

 

단순히  단어가 저장되었는지 여부를 파악하는 것이라면 Map 자료구조로 key에 대한 value가 존재하는지 조사하면 되지만, '.'으로 알파벳을 대체할 수 있기 때문에 다른 방식을 사용해야 한다.

 

따라서 이전 문제에서 공부했던 Tries를 활용해서 해결해 보았다.

 

트라이와 다른 점은 '.'은 모든 알파벳을 대체할 수 있으므로, search하는 word에 '.'이 들어간다면 모든 알파벳으로 분기할 수 있도록 해야 한다.

 

아래의 Trie 구조에서 ". ea"를 찾는다면,

첫 글자인 '.'는 t, A, i로 모두  대체될 수 있으므로 3가지 분기를 모두 확인하는 방식을 취해야 한다.

 

 

 

코드