Longest Uncommon Subsequence I

这道题挺有意思, 求惯了Longest Common Subsequence, 这次换成了uncommon, 一开始陷入dp求解, 后来仔细观察后发现字符串a和字符串b如果不想等的话, 长的字符串永远成为短字符串的subsequence, 简单吧

public class Solution {
    public int findLUSlength(String a, String b) {
        if(a.equals(b)) return -1;
        return Math.max(a.length(), b.length());
    }
}

Longest Uncommon Subsequence II

用了和第一问同样的求解思路后挂在了 ["aaa","aaa","aa"] 上, 应该返回-1, 返回了3. 错误在于aaa是aaa的subsequence, 只要有一个是subsequence, 就不符合了.

longest uncommon subsequence就是找一个string, 这个string不能是任何字符串的子序列.字符串长度由高到低排列, 找出的第一个不为其他子序列的字符串为结果.

public class Solution {
    class comp implements Comparator<String> {
        public int compare(String o1, String o2) {
            return Integer.compare(o2.length(), o1.length());
        }
    }

    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, new comp());
        for(int i=0;i<strs.length;i++){
            boolean flag = true;
            for(int j=0;j<strs.length;j++){
                if(isSub(strs[i], strs[j])&&i!=j){
                    flag = false;
                    break;
                }
            }
            if(flag) return strs[i].length();
        }
        return -1;
    }

    public boolean isSub(String s1, String s2){
        int i=0;
        for(int j=0;j<s2.length();j++){
            if(s2.charAt(j)==s1.charAt(i)){
                i++;
            }
            if(i==s1.length()) return true;
        }
        return i==s1.length();
    }
}

Longest Word in Dictionary through Deleting

这道题可以抽象为在字符串中寻找最长子序列。对字典排序后，two pointer扫就可以。1次AC。期间在考虑扫的时候短暂考虑过dp，完全没必要。89.36%，速度还行。

public class Solution {
    public String findLongestWord(String s, List<String> dict) {
        Collections.sort(dict, new Comparator<String>(){
            public int compare(String s1, String s2){
                if(s1.length()!=s2.length())
                    return s2.length()-s1.length();
                return s1.compareTo(s2);
            }
        });

        char[] arr2 = s.toCharArray();
        for(String d:dict){
            char[] arr1 = d.toCharArray();
            int idx = 0;
            for(int i=0;i<arr2.length;i++){
                if(arr1[idx]==arr2[i]) idx++;
                if(idx==arr1.length) return d;
            }
        }
        return"";
    }
}