中级农民
- 积分
- 106
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2019-8-25
- 最后登录
- 1970-1-1
|
今天学习了Trie~
211 Add and Search Word - Data Structure Design
/* For data structure design questions like this one, the basic idea is very similar to logger design questions. It is easy to come up with a solution. But the essence of the question is to acknowledge different trade-offs of ds. */
My Notes
Method 1: Brute Force
Create a linked list. To add a word, we append the word to the end of list. To search, we loop the linked list and compare each word in the list to see if it is a good fit.
Add:
Time Complexity: O(1)
Space Complexity: O(N), no extra memory
Search
Time Complexity: O(N * m), where m is the maximum length of word.
Space Complexity: O(1)
Given a word and a pattern, it is not that easy to determine if it is a match.
Method 2: Use a set to store add possible patterns for a word
Example: “dad” , we need to add
d*,* *a*, **d, dad, da*, *ad,d*d
Add:
Time Complexity: O(len)
Space O(2^len * N)
Search
Time Complexity: O(1)
Space O(1)
The short come of this method is that I think it is not really storing the words. It is designed solely to faster searching process.
Method 3: Trie
Add: O(word length)
Search: O(word length) - O(M*N)
Memory: O(n*word length*26(alphabetic a))
———————————————————————
Solution
Method 1: HashMap<Integer Word Length, Set<String>>
Time Complexity: O(M*N), where M represents length of the word, N represents number of strings at the length

Method 2: Trie
Trie implementation is pretty straightforward, it's basically nested hashmaps. At each step, one has to verify, if the child node to add is already present. If yes, just go one step down. If not, add it into the trie and then go one step down.
https://leetcode.com/problems/ad ... and-clean-Java-code
With backtracking
Class TrieNode里面 TrieNode(){}要是public TrieNode(){}
——————————————————————————————————
Related Questions
There are two main types of trie interview questions:
* Standard Trie. Design a structure to dynamically add and search strings, for example
* Add and Search Word.
* Word Search II.
* Design Search Autocomplete System.
* Bitwise Trie. Design a structure to dynamically add binary strings and compute maximum/minimum XOR/AND/etc, for example
* Maximum XOR of Two Number in an Array.
|
|