LeetCode（1268）：搜尋推薦系統 Search Suggestions System（Java）

2019.12.9 LeetCode 從零單刷個人筆記整理（持續更新）

github：https://github.com/ChopinXBP/LeetCode-Babel

這是參加的第二場周賽。

本題很直接可以想到字首樹+DFS的思路，不過要注意一點神坑：測試用例的字典中可能包含重複的單詞。應對這點，隻需要在字典樹結點中加上條件count用于統計相同單詞的出現次數即可。

也可以不直接建樹，先将字典單詞排序，每次周遊字首符合的單詞，保留集合以供下一輪周遊。多次重複周遊即可得出結果。

傳送門：搜尋推薦系統

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.

給你一個産品數組 products 和一個字元串 searchWord ，products 數組中每個産品都是一個字元串。

請你設計一個推薦系統，在依次輸入單詞 searchWord 的每一個字母後，推薦 products 數組中字首與 searchWord 相同的最多三個産品。如果字首相同的可推薦産品超過三個，請按字典序傳回最小的三個。

請你以二維清單的形式，傳回在輸入 searchWord 每個字母後相應的推薦産品的清單。

示例 1：
輸入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
輸出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解釋：按字典序排序後的産品清單是 ["mobile","moneypot","monitor","mouse","mousepad"]
輸入 m 和 mo，由于所有産品的字首都相同，是以系統傳回字典序最小的三個産品 ["mobile","moneypot","monitor"]
輸入 mou， mous 和 mouse 後系統都傳回 ["mouse","mousepad"]

示例 2：
輸入：products = ["havana"], searchWord = "havana"
輸出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：
輸入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
輸出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：
輸入：products = ["havana"], searchWord = "tatiana"
輸出：[[],[],[],[],[],[],[]]

提示：
1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字元都是小寫英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字元都是小寫英文字母。
           

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 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.
 * 給你一個産品數組 products 和一個字元串 searchWord ，products  數組中每個産品都是一個字元串。
 * 請你設計一個推薦系統，在依次輸入單詞 searchWord 的每一個字母後，推薦 products 數組中字首與 searchWord 相同的最多三個産品。如果字首相同的可推薦産品超過三個，請按字典序傳回最小的三個。
 * 請你以二維清單的形式，傳回在輸入 searchWord 每個字母後相應的推薦産品的清單。
 *
 */

public class SearchSuggestionsSystem {
    private class TrieNode{
        boolean end = false;
        String str = null;
        int count = 0;
        TrieNode[] children = new TrieNode[26];
    }

    private class Trie{
        TrieNode root = new TrieNode();
        public void insert(String[] products){
            for(String str : products){
                insertWord(str);
            }
        }
        private void insertWord(String products){
            TrieNode node = root;
            for(char c : products.toCharArray()){
                if(node.children[c - 'a'] == null){
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            if(node.end != true){
                node.end = true;
                node.str = products;
            }
            node.count++;
        }
        public List<List<String>> searchWord(String word){
            List<List<String>> result = new ArrayList<>();
            for(int i = 1; i <= word.length(); i++){
                result.add(search(word.substring(0, i)));
            }
            return result;
        }
        private List<String> search(String pattern){
            List<String> result = new ArrayList<>();
            TrieNode node = root;
            for(char c : pattern.toCharArray()){
                if(node.children[c - 'a'] == null){
                    return result;
                }
                node = node.children[c - 'a'];
            }
            Solution(node, result);
            return result;
        }
        private void Solution(TrieNode root, List<String> result){
            if(root.end){
                for(int i = 0; i < root.count; i++){
                    result.add(root.str);
                    if(result.size() == 3){
                        return;
                    }
                }
            }
            for(TrieNode node : root.children){
                if(node != null){
                    Solution(node, result);
                }
                if(result.size() == 3){
                    return;
                }
            }
        }
    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        Trie trie = new Trie();
        trie.insert(products);
        return trie.searchWord(searchWord);
    }
}



           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#