1268. Search Suggestions System - Medium

前往題目

想法

• 排好之後，Binary Search匹配searchWord，但有可能原本匹配的那些多加一個searchWod字母後就全部不匹配了，反而是最後面的匹配，這部分不知道怎麼解決

思路

解決辦法就是把區間找出來，一個一個找，慢慢收斂區間

1. 排序
2. 一個字母一個字母來
3. 雙指針，左右指針循環直到遇到匹配的字母，但要略過長度不夠的item，藉此判斷出區間
4. 區間找出後，直接把該區間加入答案裡

這題關鍵是如何找出區間，條件寫好就可以輕鬆判斷

Code

class Solution {
    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        // Base case

        // Sort the products lexicographically
        Arrays.sort(products);

        List<List<String>> res = new ArrayList<List<String>>();

        int l = 0, r = products.length - 1;
        
        // Match the word
        for (int i = 0; i < searchWord.length(); ++i) {
            char c = searchWord.charAt(i);

            // When index exceeds products' item length or it doesn't match with the character
            while (l <= r && (products[l].length() <= i || products[l].charAt(i) != c)) {
                ++l;
            }
            while (l <= r && (products[r].length() <= i || products[r].charAt(i) != c)) {
                --r;
            }

            int remainWindowLen = r - l + 1;
            List<String> tempList = new ArrayList<>();

            // Add the window
            for (int j = 0; j < Math.min(3, remainWindowLen); ++j) {
                tempList.add(products[l + j]);
            }

            // Add to the result
            res.add(tempList);
        }
        return res;
    }
}