0522. Longest Uncommon Subsequence II - kumaeki/LeetCode GitHub Wiki

0522. Longest Uncommon Subsequence II

Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.

An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.

A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.

For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).

Example 1:

Input: strs = ["aba","cdc","eae"]

Output: 3

Example 2:

Input: strs = ["aaa","aaa","aa"]

Output: -1

Constraints:

  • 1 <= strs.length <= 50
  • 1 <= strs[i].length <= 10
  • strs[i] consists of lowercase English letters.

解法1

class Solution {
    public int findLUSlength(String[] strs) {
        
        Arrays.sort(strs, (a, b) -> b.length() - a.length());

        // 得到重复的字符串的set
        Set<String> dup = getDuplicates(strs);
        
        for(int i = 0; i < strs.length; i++) {
            if(!dup.contains(strs[i])) {
                
                // 单独判断最长的字符串
                if(i == 0) return strs[0].length();
                
                if(!isSub(strs[0], strs[i]))
                    return strs[i].length();
            }
        }
        
        return -1;
    }
    
    // 得到重复的字符串的set
    private Set<String> getDuplicates(String[] strs){
        Set<String> set = new HashSet<>(), result = new HashSet<>();
        for(String s : strs){
            if(set.contains(s)) result.add(s);
            else set.add(s);
        }
        return result;
    }
    
    // 判断s2是否是s1的字串
    private boolean isSub(String s1, String s2){
        int len1 = s1.length(), len2 = s2.length();
        
        if(len1 == len2) return s1.equals(s2);
        
        int i1 = 0, i2 = 0;
        while(i1 < len1 && i2 < len2 && len1 - i1 >= len2 - i2 ){
            if(s1.charAt(i1) == s2.charAt(i2))
                i2++;
            i1++;
        }
        
        return i2 == len2;
    }
}

解法2

HashMap.

class Solution {
    public int findLUSlength(String[] strs) {
        Map<String, Integer> subseqFreq = new HashMap<>();
        for (String s : strs) 
            for (String subSeq : getSubseqs(s))
                subseqFreq.put(subSeq, subseqFreq.getOrDefault(subSeq, 0) + 1);
        int longest = -1;
        for (Map.Entry<String, Integer> entry : subseqFreq.entrySet()) 
            if (entry.getValue() == 1) longest = Math.max(longest, entry.getKey().length());
        return longest;
    }

    public static Set<String> getSubseqs(String s) {
        Set<String> res = new HashSet<>();
        if (s.length() == 0) {
             res.add("");
             return res;
        }
        Set<String> subRes = getSubseqs(s.substring(1));
        res.addAll(subRes);
        for (String seq : subRes) res.add(s.charAt(0) + seq);
        return res;
    }
}
⚠️ **GitHub.com Fallback** ⚠️