leetcode 1268. Search suggestions system

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”]

Similar to Baidu , bing Inside , Input a word and the function of recommending relevant terms will appear automatically .
At most, only 3 A word , The candidate entry is products The words inside .
searchWord There will be a maximum of each letter when you type 3 Recommended words .

Ideas ：
1.Trie + DFS
Words with this prefix usually think of Trie, The first is to build Trie structure ,
Because when the prefixes are the same, they should be sorted by dictionary order , So after the prefix search, press a~z Search in the order of .
Search with DFS,
Because there are only 26 individual , So each node has 26 Letters .
But this method is complex and time-consuming .

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 The rest is searched alphabetically 
        for(char c = 'a'; c <= 'z'; c ++) {
    
            if(curr.children.get(c - 'a') != null) {
      // With this letter child
                dfsWithPrefix(curr.children.get(c - 'a'), word + c);  // from child Start searching down 
            }
        }
    }
    
    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. Double pointer
The premise of double pointer is, of course, to give products Array sorting .
When left The word that points to products[ left ] The length of < searchWord perhaps When the middle letters are inconsistent , explain searchWord Can't be products[left] The prefix of this word ,
At this time left ++,
In the same way products[ right ] The length of < searchWord perhaps When there are inconsistent letters in the middle , explain searchWord Can't be treated as products[ right ] The prefix of this word ,
At this time right --,
When products[left] and products[right] Both contain searchWord As a prefix , Just take it from left to right 3 Just one word , When the number of words in this range <3 when , take left ~ right All words in the range .

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;
}