1268. Search Suggestions System - kumaeki/LeetCode GitHub Wiki
1268. Search Suggestions System
Given an array of strings products and a string searchWord.
We want to 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 the searchWord.
If there are more than three products with a common prefix return the three lexicographically minimums products.
Return 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"]
Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Example 3:
Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
Example 4:
Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]
Constraints:
- 1 <= products.length <= 1000
- There are no repeated elements in products.
- 1 <= Σ products[i].length <= 2 * 10^4
- All characters of products[i] are lower-case English letters.
- 1 <= searchWord.length <= 1000
- All characters of searchWord are lower-case English letters.
用字典来储存字符串, 然后再去遍历查找所有可能的字符串.
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> res = new ArrayList<List<String>>();
// 初始化字典
Node root = new Node('#');
for(String p : products)
insertPro(root, p.toCharArray(), 0);
// 遍历所有可能的子字符串
for(int i = 1; i <= searchWord.length(); i++)
res.add(getProduct(searchWord.substring(0, i), root));
return res;
}
//
private List<String> getProduct(String word, Node node){
List<String> res = new ArrayList<String>();
// 找到word最后一个字符在字典中的位置
for(char c : word.toCharArray()){
if(node.next[c - 'a'] == null)
return res;
node = node.next[c - 'a'];
}
// 从该位置往后查找3个字符串
getStr(word, node, res);
return res;
}
// 从node位置往后查找3个字符串
private void getStr(String word, Node node, List<String> res) {
if (res.size() == 3)
return;
if (node.isEnd)
res.add(word);
for (Node next : node.next)
if (next != null)
getStr(word + next.val, next, res);
}
// 初始化字典
private void insertPro(Node node, char[] arr, int i){
if(i == arr.length){
node.setEnd();
return;
}
char c = arr[i];
if(node.next[c - 'a'] == null){
node.next[c - 'a'] = new Node(c);
}
insertPro(node.next[c - 'a'], arr, i + 1);
}
// 字典的node定义
class Node{
char val;
Node[] next;
boolean isEnd;
public Node(char c){
val = c;
next = new Node[26];
isEnd = false;
}
public void setEnd(){
isEnd = true;
}
}
}解法1中每次都重新从root开始查找, 进行了很多重复查找.
这里稍微改进了一下
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> res = new ArrayList<List<String>>();
// 初始化字典
Node root = new Node('#');
for(String p : products)
insertPro(root, p.toCharArray(), 0);
getProduct(searchWord, root, res, true);
return res;
}
private void getProduct(String word, Node node, List<List<String>> res, boolean isMatch){
// 遍历word
for(int i = 1; i <= word.length(); i++){
List<String> list = new ArrayList<String>();
// 如果字符在字典中存在, 那么将空列表加入结果集
char c = word.charAt(i - 1);
if(isMatch){
if(node.next[c - 'a'] != null){
node = node.next[c - 'a'];
getStr(word.substring(0, i), node, list);
}else
isMatch = false;
}
res.add(list);
}
}
// 从node位置往后查找3个字符串
private void getStr(String word, Node node, List<String> res) {
if (res.size() == 3)
return;
if (node.isEnd)
res.add(word);
for (Node next : node.next)
if (next != null)
getStr(word + next.val, next, res);
}
// 初始化字典
private void insertPro(Node node, char[] arr, int i){
if(i == arr.length){
node.setEnd();
return;
}
char c = arr[i];
if(node.next[c - 'a'] == null){
node.next[c - 'a'] = new Node(c);
}
insertPro(node.next[c - 'a'], arr, i + 1);
}
// 字典的node定义
class Node{
char val;
Node[] next;
boolean isEnd;
public Node(char c){
val = c;
next = new Node[26];
isEnd = false;
}
public void setEnd(){
isEnd = true;
}
}
}这里要求每个搜索返回3个结果,而且不会在中途再次更改字典.
所以在通用的地点上做一些优化, 直接在节点中储存当前节点的3个搜索结果.
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
List<List<String>> res = new ArrayList<List<String>>();
Arrays.sort(products);
// 初始化字典
Node root = new Node();
for(String p : products)
insertPro(root, p, 0);
getProduct(searchWord, root, res, true);
return res;
}
private void getProduct(String word, Node node, List<List<String>> res, boolean isMatch){
// 遍历word
for(int i = 1; i <= word.length(); i++){
int index = word.charAt(i - 1) - 'a';
if(isMatch && node.next[index] != null){
node = node.next[index];
res.add(node.list);
}else{
isMatch = false;
res.add(new ArrayList<String>());
}
}
}
// 初始化字典
private void insertPro(Node node, String word, int i){
if(i == word.length()){
return;
}
int index = word.charAt(i) - 'a';
if(node.next[index] == null){
node.next[index] = new Node();
}
if(node.next[index].list.size() < 3)
node.next[index].list.add(word);
insertPro(node.next[index], word, i + 1);
}
// 字典的node定义
class Node{
Node[] next;
List<String> list;
public Node(){
next = new Node[26];
list = new ArrayList<String>();
}
}
}