You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = [“mobile”,“mouse”,“moneypot”,“monitor”,“mousepad”], searchWord = “mouse”
Output: [
[“mobile”,“moneypot”,“monitor”],
[“mobile”,“moneypot”,“monitor”],
[“mouse”,“mousepad”],
[“mouse”,“mousepad”],
[“mouse”,“mousepad”]
]
Explanation: products sorted lexicographically = [“mobile”,“moneypot”,“monitor”,“mouse”,“mousepad”]
After typing m and mo all products match and we show user [“mobile”,“moneypot”,“monitor”]
After typing mou, mous and mouse the system suggests [“mouse”,“mousepad”]
类似在百度, bing里面，输入一个字就会自动出现推荐的相关词条的功能。
这里最多只推荐3个词条，候选词条就是products里面的单词。
searchWord的每个字母输入的时候都会有最多3个推荐词条。
思路：
1.Trie + DFS
这种前缀的单词一般会想到Trie, 首先就是构建Trie结构，
因为前缀一样时后面要按字典顺序排序，所以前缀搜索完之后就按a~z的顺序搜索。
搜索时用DFS,
因为英文字母只有26个，所以每个节点有26个字母。
但这种方法比较复杂且耗时较长。
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Trie trie = new Trie();
List<List<String>> result = new ArrayList<>();
for(String w : products)
trie.insert(w);
String prefix = new String();
for(char c : searchWord.toCharArray()) {
prefix += c;
result.add(trie.getWordsStartingWith(prefix));
}
return result;
}
}
class Trie {
class Node {
boolean isWord = false;
List<Node> children = Arrays.asList(new Node[26]);
};
Node Root, curr;
List<String> resultBuffer;
void dfsWithPrefix(Node curr, String word) {
if(resultBuffer.size() == 3) return;
if(curr.isWord) resultBuffer.add(word);
//prefix剩下的部分按字母顺序搜索
for(char c = 'a'; c <= 'z'; c ++) {
if(curr.children.get(c - 'a') != null) { //有这个字母的child
dfsWithPrefix(curr.children.get(c - 'a'), word + c); //从child开始往下搜索
}
}
}
Trie() {
Root = new Node();
}
void insert(String s) {
curr = Root;
for(char c : s.toCharArray()) {
if(curr.children.get(c - 'a') == null)
curr.children.set(c - 'a', new Node());
curr = curr.children.get(c - 'a');
}
curr.isWord = true;
}
List<String> getWordsStartingWith(String prefix) {
curr = Root;
resultBuffer = new ArrayList<String>();
for(char c : prefix.toCharArray()) {
if(curr.children.get(c - 'a') == null) return resultBuffer;
curr = curr.children.get(c - 'a');
}
dfsWithPrefix(curr, prefix);
return resultBuffer;
}
}
2.双指针
双指针的前提当然是先要给products数组排序。
当 left 指向的单词 products[ left ] 的长度 < searchWord 或者 中间字母有不一致的情况时，说明searchWord不能当products[left] 这个单词的前缀，
这时 left ++,
同理当 products[ right ]的长度 < searchWord 或者 中间有字母不一致的情况时，说明searchWord不能当作 products[ right ] 这个单词的前缀，
这时right --，
当 products[left] 和 products[right] 都含有 searchWord作为前缀时，只需要从左到右取3个单词即可，当这个范围内的单词数量<3时，取left ~ right范围内的所有单词。
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> list = new ArrayList<>();
Arrays.sort(products);
int n = searchWord.length();
int l = 0,r = products.length-1;
for(int i = 0;i<n;i++) {
char ch = searchWord.charAt(i);
while(l <= r && (products[l].length() <= i || products[l].charAt(i) != ch )) {
l++;
}
while(l <= r && (products[r].length() <= i || products[r].charAt(i) != ch )) {
r--;
}
int x = r - l + 1;
ArrayList<String> lis = new ArrayList<>();
for(int j = 0;j<Math.min(x,3);j++) {
lis.add(products[j+l]);
}
list.add(lis);
}
return list;
}