BiruLyu
7/14/2017 - 7:31 PM

524. Longest Word in Dictionary through Deleting(1st).java

public class Solution {
    public boolean isSubsequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
    public String findLongestWord(String s, List < String > d) {
        Collections.sort(d, new Comparator < String > () {
            public int compare(String s1, String s2) {
                return s2.length() != s1.length() ? s2.length() - s1.length() : s1.compareTo(s2);
            }
        });
        for (String str: d) {
            if (isSubsequence(str, s))
                return str;
        }
        return "";
    }
}
public class Solution {
    public boolean isSubsequence(String x, String y) {
        int j = 0;
        for (int i = 0; i < y.length() && j < x.length(); i++)
            if (x.charAt(j) == y.charAt(i))
                j++;
        return j == x.length();
    }
    public String findLongestWord(String s, List < String > d) {
        String max_str = "";
        for (String str: d) {
            if (isSubsequence(str, s)) {
                if (str.length() > max_str.length() || (str.length() == max_str.length() && str.compareTo(max_str) < 0))
                    max_str = str;
            }
        }
        return max_str;
    }
}
public class Solution {
    public String findLongestWord(String s, List<String> d) {
        String c = "";
        for(int i =0;i<d.size();i++){
            String ch = d.get(i);
            boolean flag = compareString(s, ch);
            if(flag){
                if(ch.length() > c.length()){
                    c = ch;
                }else if(c.length() == ch.length()){
                    if(ch.compareTo(c) < 0){
                        c = ch;
                    }
                }
            }
        }
        return c;
    }

    public boolean compareString(String s, String t){
        int k = 0;
        if(t.equals(s)){
            return true;
        }
        int index = 0;
        for(int i=0;i<t.length();i++){
            index = s.indexOf(t.charAt(i), index);
            if(index < 0){
                break;
            }else{
                index += 1;
            }
            k++;
        }
        if(k == t.length()){
            return true;
        }
        return false;
    }
}