2021-09-14 LeetCode每日一題
鏈接：https://leetcode-cn.com/problems/longest-word-in-dictionary-through-deleting/
標(biāo)簽：數(shù)組、雙指針、字符串、排序
題目
給你一個字符串 s 和一個字符串?dāng)?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] 僅由小寫英文字母組成
分析
返回長度最長且字典序最小的字符串宫补。所以我們需要先給列表排個序檬姥，最好是按字典序倒序排，如果正序排的粉怕，反向遍歷也是可以的健民。
排好序后，其實就是用字符串和目標(biāo)字符串s進(jìn)行比較了贫贝，這里可以使用雙指針分別執(zhí)行字符串和目標(biāo)字符串秉犹，如果相等則一起移動，不相等移動一個稚晚。
可以優(yōu)化的點崇堵，就是在比較之前，可以先判斷字符串的長度是否大于等于當(dāng)前符合條件的最長字符串的長度客燕，如果小于那不用比較了鸳劳，肯定不是最優(yōu)解。另外如果字符串長度大于目標(biāo)字符串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片描述
