[String]524. Longest Word in Dictionary through Deleting

524. Longest Word in Dictionary through Deleting

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:
All the strings in the input will only contain lower-case letters.
The size of the dictionary won't exceed 1,000.
The length of all the strings in the input won't exceed 1,000.

两个指针。
一开始用flag，写的很乱，关键flag回到false的位置没对，折腾了很久才发现这个问题。Runtime: 72 ms

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int max_len = 0;
        String res = "";
        for(String word : d){
            int index = 0;
            boolean flag = false;
            for(int i = 0; i<word.length(); i++){
                flag = false;//**!! Must Return to Default!!**
                for(int j = index; j<s.length(); j++){
                    if(s.charAt(j) == word.charAt(i)){
                        index = j+1;
                        flag = true;
                        break;
                    }
                    flag = false;//some char in the word cannot be matched
                }
                if(flag == false) break;//string search is finished, word isn't
            }
            
            if(flag == true && word.length() >= max_len){
                if(word.length() > max_len || word.compareTo(res)<0){
                    // System.out.println(word+"--"+res+"="+word.compareTo(res));
                    res = word;
                    max_len = word.length();
                }
                // System.out.println(word+"-"+res+"="+word.compareTo(res));
            } 
        }
        return res;
    }
}

大神指点后不用flag清晰多了。55 ms

class Solution {
    public String findLongestWord(String s, List<String> d) {
        int max_len = 0;
        String res = "";
        for(String word : d){
            int index = 0;
            int i = 0;
            for(; i<word.length(); i++){
                int j = index;
                for(; j<s.length(); j++){
                    if(s.charAt(j) == word.charAt(i)){
                        index = j+1;
                        break;
                    }
                }
                if(j == s.length()) break;//string search is finished, char[j] isn't in string, next word 

            }
            
            if(i == word.length()  && word.length() >= max_len){
                if(word.length() > max_len || word.compareTo(res)<0){
                    res = word;
                    max_len = word.length();
                }
            }
       
        }
        return res;
        
    }
}