题目信息
LeetoCode地址: 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
题目理解
这道题的题意不难理解，在我们使用搜索引擎的每一天都会遇到，不需要输入完整的关键词，哪怕仅仅只输入一个字，搜索引擎就会自动返回若干以这个字开头的若干查询结果，比如最近爆火的《繁花》电视剧
该题目是搜索引擎的极致简化版，每个字符都是a-z这26个小写字母。
如果你做过Trie 树相关的题目，很容就能联想到该题目可以以同样的方式求解，当我们建立好Trie 树之后，只要按照searchWord的每个字符进行逐个匹配直到最后一个字符，这时在按字典序查找最多3个以该字符为前缀的终止字符串。
这里就不对过程详细展开了，需要的同学可以回顾下面两篇文章。
实现Trie 字典树：CSDN
添加与搜索单词：CSDN
Trie树 写法
详细过程就不论述了，需要注意的是，在从第1个字符逐次递增一个字符进行搜索时，每一次都可以从上一次结尾的Trie 节点开始，而无需每次都从第0个字符开始，以节省时间。
在products树组长度为n,每个product字符串平均长度为m,searchWord字符串长度为s的情况下:
搜索 时间复杂度: O(s *26^m)，在每一次遍历节点是，理论最坏qingdfs最多会调用product字符串长度层，每次都会遍历26个字符。
额外空间复杂度:O(n*m), 用于存储Trie树节点。
Trie root;
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
root = new Trie();
for (String product : products) {
addWord(product);
}
List<List<String>> result = new ArrayList<>();
Trie lastEndTrie = root;
for (int i = 0; i< searchWord.length(); i++) {
List<String> current = new ArrayList<>();
lastEndTrie = search(lastEndTrie, searchWord, i, current);
result.add(current);
}
return result;
}
public Trie search(Trie lastEndTrie, String word, int index, List<String> list) {
if (lastEndTrie == null) {
return null;
}
int indexOfChar = word.charAt(index) - 'a';
Trie next = lastEndTrie.nextList[indexOfChar];
if (next != null) {
lastEndTrie = next;
} else {
return null;
}
dfs(lastEndTrie, list);
return lastEndTrie;
}
public void addWord(String word) {
Trie current = root;
for (char c : word.toCharArray()) {
if (current.nextList[c-'a'] != null) {
current = current.nextList[c-'a'];
} else {
Trie next = new Trie();
current.nextList[c-'a'] = next;
current = next;
}
}
current.value = word;
current.end = true;
}
private void dfs(Trie current, List<String> list) {
if (list.size() == 3 || current == null) {
return;
}
if (current.end) {
list.add(current.value);
}
for (Trie trie : current.nextList) {
if (trie != null) {
dfs(trie, list);
}
}
}
class Trie {
boolean end;
String value;
Trie[] nextList;
public Trie() {
this.end = false;
this.nextList = new Trie[26];
}
}排序+双指针 写法
其实当题目提到“按字典序返回最小的三个” 这样的描述时，我们就要很警觉了，因为很可能和与排序有关系。
假如我们先将products按照字典序进行排序，然后确定满足当前searchWord的product的左右下标区间，则该区间最左侧的三个元素就是题目要求的字典序最小的三个元素。
更妙的是，假设我们当前搜索匹配的字符串是searchWord的0到i字串，当我们递增i匹配0到i+1字传时，完全不需要从头确定products的左右下标，直接基于上一次遍历的下标基础上进行类似的缩小范围即可。
那么缩小范围的逻辑是什么呢？其实也是很直观的。
- 初始来看，左下标l=0, 右下标r=products.length-1. 毫无疑问l<=r 是必须保证的
- 其次，下标l对应的的product，其长度必须大于等于当前searchWord下标i，否则就要向右移动l. 当product[l]的第i个字符与searchWord的第i个字符不相符时，也不满足题目前缀的要求，也应该向右移动l.
- 类似的，下标r对应的的product，其长度必须大于等于当前searchWord下标i，否则就要向左移动r. 当product[r]的第i个字符与searchWord的第i个字符不相符时，也不满足题目前缀的要求，也应该向左移动r.
当l和r位置在当前i的值下都确定之后，就可以将区间内的前三个元素放入结果集中，然后对i递增，进行下一轮的遍历，直到遍历完所有的字符。
在products树组长度为n,每个product字符串平均长度为m,searchWord字符串长度为s的情况下:
搜索 时间复杂度: O(n)，l向右移动，r向左移动，直到相遇为止，最多会移动products的长度那么多步。
额外空间复杂度:O(1),由于所有操作都在原树组上进行，我们只需要几个下标变量，仅需要常数规模的空间存储。
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
int l = 0, r = products.length-1;
List<List<String>> result = new ArrayList<>();
for (int i = 0; i < searchWord.length(); i++) {
while (l < r && (products[l].length() <= i || products[l].charAt(i) != searchWord.charAt(i))) {
l++;
}
while (l < r && (products[r].length() <= i || products[r].charAt(i) != searchWord.charAt(i))) {
r--;
}
List<String> temp = new ArrayList<>();
for (int ii = l; ii<=r && ii+3 <=r; ii++) {
temp.add(products[ii]);
}
result.add(temp);
}
return result;
}
