2021-09-14 LeetCode每日一題

鏈接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/

標簽：數(shù)組、雙指針、字符串、排序

題目

給你一個字符串 s 和一個字符串數(shù)組 dictionary 作為字典，找出并返回字典中最長的字符串，該字符串可以通過刪除 s 中的某些字符得到。

如果答案不止一個，返回長度最長且字典序最小的字符串。如果答案不存在，則返回空字符串。

示例 1：

輸入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
輸出："apple"

示例 2：

輸入：s = "abpcplea", dictionary = ["a","b","c"]
輸出："a"

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 僅由小寫英文字母組成

分析

返回長度最長且字典序最小的字符串。所以我們需要先給列表排個序，最好是按字典序倒序排，如果正序排的，反向遍歷也是可以的。

排好序后，其實就是用字符串和目標字符串s進行比較了，這里可以使用雙指針分別執(zhí)行字符串和目標字符串，如果相等則一起移動，不相等移動一個。

可以優(yōu)化的點，就是在比較之前，可以先判斷字符串的長度是否大于等于當前符合條件的最長字符串的長度，如果小于那不用比較了，肯定不是最優(yōu)解。另外如果字符串長度大于目標字符串s的長度，那么也不用比較了。

編碼

class Solution {
    public String findLongestWord(String s, List<String> dictionary) {
        // 自然排序
        dictionary.sort(String.CASE_INSENSITIVE_ORDER);
        int max = 0, sLen = s.length();
        String res = "";

        // 反向遍歷
        for (int i = dictionary.size() - 1; i >= 0; --i) {
            String str = dictionary.get(i);
            int len = str.length();
            if (len > sLen || len < max) {
                continue;
            }
            int left = 0, right = 0, count = 0;
            while (right < sLen && left < len) {
                if (str.charAt(left) == s.charAt(right)) {
                    left++;
                    right++;
                    count++;
                } else {
                    right++;
                }
            }

            if (count == len && count >= max) {
                max = count;
                res = str;
            }
        }

        return res;
    }
}

請?zhí)砑訄D片描述