【LeetCode】524-通過刪除字母匹配到字典里最長單詞
題目描述
給定一個字元串和一個字元串字典,找到字典裡面最長的字元串,該字元串可以通過刪除給定字元串的某些字元來得到。如果答案不止一個,返回長度最長且字典順序最小的字元串。如果答案不存在,則返回空字元串。
示例 1:
輸入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
輸出:
"apple"
示例 2:
輸入:
s = "abpcplea", d = ["a","b","c"]
輸出:
"a"
說明:
- 所有輸入的字元串只包含小寫字母。
- 字典的大小不會超過 1000。
- 所有輸入的字元串長度不會超過 1000。
解題思路
- 通過雙指針查看字典中的一個字元串是不是給定字元串的子序列
- 通過
compareTo
在同樣長度下,找到字典順序更小的那個
public String findLongestWord(String s, List<String> d) {
String longestWord = "";
for (String str : d){
int l1 = longestWord.length();
int l2 = str.length();
if (isSubsequence(s, str)){
if (l2 > l1 || (l2 == l1) && str.compareTo(longestWord)<0)
longestWord = str;
}
}
return longestWord;
}
private boolean isSubsequence(String s, String target){
int i = 0, j = 0;
while (i < s.length() && j < target.length()){
if (s.charAt(i) == target.charAt(j))
j++;
i++;
}
return j == target.length();
}
推薦閱讀: