这是一道medium的题目，题目要求给一个字符串S，一个string array 的dictionary ， 找出S删除某些字符后可以生成的在dictionary里面的最长的string，如果长度相同则按字符顺序返回最小字符顺序的string。
solution: two pointers,
my solution:
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
String longest = "";
for(String target : dictionary) {
if(target.length() < longest.length()) {
continue;
}
if(target.length() == longest.length() && longest.compareTo(target) <0) {
continue;
}
int i = 0, j=0;
while(i<target.length() && j <s.length()) {
if(target.charAt(i) == s.charAt(j)) {
i++;
}
j++;
}
if(i==target.length()) {
longest = target;
}
}
return longest;
}
}
time complexity: O(nm), n is s's length, m is the number of strings in dictionary. because there's a loop for dictionary.
space complexity: O(x), x is the length of max length string which we stored
网友评论