522. Longest Uncommon Subsequence II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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:

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

Code

class Solution {
    public int findLUSlength(String[] strs) {
        Arrays.sort(strs, (s1, s2) -> s2.length() - s1.length());
        
        for (int i = 0; i < strs.length; i++) {
            String curr = strs[i];
            
            int count = 0;
            for (int j = 0; j < strs.length; j++) {
                if (i != j && !isSub(curr, strs[j])) {
                    count++;
                }
            }
            
            if (count == strs.length - 1) {
                return curr.length();                
            }
        }
        
        return -1;
    }
    
    public boolean isSub(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        
        int index = 0;
        
        for (int i = 0; i < s2.length(); i++) {
            if(index == s1.length()) return true;
            
            if (s1.charAt(index) == s2.charAt(i)) index++;
        }
           
        return index == s1.length();
    }
}