問題:
Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.
Example 1:Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
Output:
"apple"Example 2:
Input:
s = "abpcplea", d = ["a","b","c"]
Output:
"a"Note:
1欣鳖、All the strings in the input will only contain lower-case letters.
2田巴、The size of the dictionary won't exceed 1,000.
3、The length of all the strings in the input won't exceed 1,000.
大意:
給出一個(gè)字符串和字符串字典空盼,找到字典中能夠通過刪除目標(biāo)字符串一些字符來匹配到的最長(zhǎng)的字符串。如果有多個(gè)結(jié)果册着,返回最長(zhǎng)字符串中詞典順序最小的一個(gè)褐着。如果沒有結(jié)果,返回空字符串豆挽。
例1:輸入:
s = "abpcplea", d = ["ale","apple","monkey","plea"]
輸出:
"apple"例2:
輸入:
s = "abpcplea", d = ["a","b","c"]
輸出:
"a"注意:
1育谬、所有輸入的字符串都只包含小寫字母
2、字典的大小不會(huì)超過1000帮哈。
3膛檀、所有輸入的字符串的長(zhǎng)度不會(huì)超過1000。
思路:
遍歷字典中的字符串娘侍,對(duì)每個(gè)字符串的每個(gè)字符按照順序在目標(biāo)字符串中找位置咖刃,為了保持順序,每次找下一個(gè)字符的位置時(shí)都要從上一個(gè)找到的位置之后開始找憾筏,一旦某個(gè)字符找不到僵缺,就說明不匹配。
如果一個(gè)字符串能夠匹配到踩叭,那么就看他的長(zhǎng)度是多少磕潮,根據(jù)長(zhǎng)度來更新記錄的結(jié)果翠胰,如果長(zhǎng)度一致,那就要根據(jù)兩個(gè)字符串中的字符順序來判斷留哪個(gè)了自脯。
代碼:
public class Solution {
public String findLongestWord(String s, List<String> d) {
String res = "";
int longest = 0;
for (int i = 0; i < d.size(); i++) {
String temp = d.get(i);
int last = 0;
boolean match = true;
for (int j = 0; j < temp.length(); j++) {
int index = s.indexOf(temp.substring(j, j+1), last) + 1;
if (index == 0) match = false;
else last = index;
}
if (match && temp.length() > longest) {
longest = temp.length();
res = temp;
} else if (match && temp.length() == longest) {
for (int j = 0; j < temp.length(); j++) {
if (temp.charAt(j) - res.charAt(j) < 0) {
res = temp;
break;
} else if (temp.charAt(j) - res.charAt(j) > 0) {
break;
}
}
}
}
return res;
}
}
合集:https://github.com/Cloudox/LeetCode-Record