Given a list of strings, you need to find the longest uncommon subsequence among them. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not beanysubsequence of the other strings.

Asubsequenceis a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be a list of strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.

Example 1:

Input: "aba", "cdc", "eae"

Output: 3

Solution: 为了找到最长的,先把数组按string长度由大到小排序,然后两两比较,当某一字符串不是其他的common subsequence时,返回它的长度

    public int findLUSlength(String[] strs) {
        // Sort by length in descending order to ensure first uncommon subseq is longest
        Arrays.sort(strs, (s1, s2) -> Integer.compare(s2.length(), s1.length()));

        // Compare each str if it's subseq of any other except itself
        int n = strs.length;
        for (int i = 0; i < n; i++) {
            int subseq = n;
            for (int j = 0; j < n; j++, subseq--) {
                if (i != j && isSubseq(strs[i], strs[j])) break;
            }
            if (subseq == 0) return strs[i].length();
        }
        return -1;
    }

    // Leetcode-392 Is Subsequence: O(M+N), binary search, DP...
    private boolean isSubseq(String s1, String s2) {
        int i = 0, m = s1.length(), n = s2.length();
        for (int j = 0; i < m && j < n; j++) {
            if (s1.charAt(i) == s2.charAt(j)) i++;
        }
        return i == m;
    }

results matching ""

    No results matching ""