Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
[LeetCode] 211. Design Add and Search Words Data Structure (C++)
EVEerNew 2023. 7. 12. 14:08문제
https://leetcode.com/problems/design-add-and-search-words-data-structure/
Design Add and Search Words Data Structure - LeetCode
Can you solve this real interview question? Design Add and Search Words Data Structure - Design a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: * WordDictionar
leetcode.com
풀이
난이도: Medium
단순히 단어가 저장되었는지 여부를 파악하는 것이라면 Map 자료구조로 key에 대한 value가 존재하는지 조사하면 되지만, '.'으로 알파벳을 대체할 수 있기 때문에 다른 방식을 사용해야 한다.
따라서 이전 문제에서 공부했던 Tries를 활용해서 해결해 보았다.
트라이와 다른 점은 '.'은 모든 알파벳을 대체할 수 있으므로, search하는 word에 '.'이 들어간다면 모든 알파벳으로 분기할 수 있도록 해야 한다.
아래의 Trie 구조에서 ". ea"를 찾는다면,
첫 글자인 '.'는 t, A, i로 모두 대체될 수 있으므로 3가지 분기를 모두 확인하는 방식을 취해야 한다.
코드
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 347. Top K Frequent Elements (C++) (0) | 2023.07.17 |
|---|---|
| [LeetCode] 212. Word Search II (C++) (0) | 2023.07.15 |
| [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree (C++) (0) | 2023.07.07 |
| [LeetCode] 230. Kth Smallest Element in a BST (C++) (0) | 2023.07.06 |
| [LeetCode] 98. Validate Binary Search Tree (C++) (0) | 2023.07.05 |