1268. 搜索推荐系统

解法一

模拟。每次的候选单词都是上一次的子集。

import java.util.*;
class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> ans = new ArrayList<>(searchWord.length());
        List<String> last = new ArrayList<>(searchWord.length());
        for (String str : products) {
            if (str.charAt(0) == searchWord.charAt(0)) {
                last.add(str);
            }
        }
        Comparator<String> stringComparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return o1.compareTo(o2);
            }
        };
        last.sort(stringComparator);
        if (last.size() > 3) {
            ans.add(last.subList(0, 3));
        } else {
            ans.add(last);
        }
        for (int i = 1; i < searchWord.length(); ++i) {
            String prefix = searchWord.substring(0, i + 1);
            List<String> current = new ArrayList<>(last.size());
            Iterator<String> iterator = last.listIterator();
            while (iterator.hasNext()) {
                String str = iterator.next();
                if (str.startsWith(prefix)) {
                    current.add(str);
                }
            }
            if (current.size() > 3) {
                ans.add(current.subList(0, 3));
            } else {
                ans.add(current);
            }
            last = current;
        }
        return ans;
    }
}