/**
 *  522. 最長特殊序列 II
 *  給定字符串列表，你需要從它們中找出最長的特殊序列瓤漏。
 *  最長特殊序列定義如下：該序列為某字符串獨有的最長子序列（即不能是其他字符串的子序列）宰衙。
 *  子序列可以通過刪去字符串中的某些字符實現(xiàn)荠呐，但不能改變剩余字符的相對順序。
 *  空序列為所有字符串的子序列匠楚，任何字符串為其自身的子序列良哲。
 *  輸入將是一個字符串列表，輸出是最長特殊序列的長度系任。如果最長特殊序列不存在，返回 -1 虐块。
 *
 *  示例：
 *  輸入: "aba", "cdc", "eae"
 *  輸出: 3
 *
 *  提示：
 *  1俩滥、所有給定的字符串長度不會超過 10 。
 *  2贺奠、給定字符串列表的長度將在 [2, 50 ] 之間霜旧。
 *
 */

/**
 *   方法一：檢查每個字符串
 *   如果存在這樣的特殊序列，那么它一定是某個給定的字符串儡率。
 *   檢查每個字符串是否是其他字符串的子序列挂据。如果不是，則它是一個特殊序列儿普。最后返回長度最大的特殊序列崎逃。如果不存在特殊序列，返回 -1眉孩。
 */
public int findLUSlength(String[] strs) {
    int res = -1;
    for (int i = 0, j; i < strs.length; i++) {
        for (j = 0; j < strs.length; j++) {
            if (j == i)
                continue;
            if (isSubsequence(strs[i], strs[j]))
                break;
        }
        if (j == strs.length)
            res = Math.max(res, strs[i].length());
    }
    return res;
}

public boolean isSubsequence(String s, String t) {
    int j = 0;
    for (int i = 0; j < s.length() && i < t.length(); i++)
        if (s.charAt(j) == t.charAt(i))
            j++;
    return j == s.length();
}

/**
 *   復雜度分析
 *   時間復雜度：O(x*n^2)其中 n是字符串的數(shù)量个绍，x是每個字符串的平均長度。
 *   空間復雜度：O(1)勺像，恒定的額外空間障贸。
 */


/**
 *   方法二：排序+檢查每個字符串
 *   方法一中需要判斷每個字符串是否為特殊序列错森。如果最開始可以先將所有字符串排序吟宦，則可以節(jié)省一部分計算。
 *   本方法中涩维，首先按照長度降序排序所有字符串殃姓。然后，依次使用序列中的每個字符串與其他字符串比較瓦阐，如果不存在字符串是當前字符串的子序列蜗侈，則返回當前字符串的長度。否則返回 -1睡蟋。
 */
public int findLUSlength2(String[] strs) {
    Arrays.sort(strs, new Comparator< String >() {
        public int compare(String s1, String s2) {
            return s2.length() - s1.length();
        }
    });
    for (int i = 0, j; i < strs.length; i++) {
        boolean flag = true;
        for (j = 0; j < strs.length; j++) {
            if (i == j)
                continue;
            if (isSubsequence(strs[i], strs[j])) {
                flag = false;
                break;
            }
        }
        if (flag)
            return strs[i].length();
    }
    return -1;
}

/**
 *   復雜度分析
 *   時間復雜度：O(x*n^2)其中 n 是字符串的數(shù)量踏幻，x 是每個字符串的平均長度。
 *   空間復雜度：O(1)戳杀，恒定的額外空間该面。
 */

更多LeetCode題目解法傳送門