?這是一道m(xù)edium的題目，題目要求給一個字符串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
