Python, Simple Explanation


  • 26

    When we add a letter Y to our candidate longest uncommon subsequence answer of X, it only makes it strictly harder to find a common subsequence. Thus our candidate longest uncommon subsequences will be chosen from the group of words itself.

    Suppose we have some candidate X. We only need to check whether X is not a subsequence of any of the other words Y. To save some time, we could have quickly ruled out Y when len(Y) < len(X), either by adding "if len(w1) > len(w2): return False" or enumerating over A[:i] (and checking neighbors for equality.) However, the problem has such small input constraints that this is not required.

    We want the max length of all candidates with the desired property, so we check candidates in descending order of length. When we find a suitable one, we know it must be the best global answer.

    def subseq(w1, w2):
        #True iff word1 is a subsequence of word2.
        i = 0
        for c in w2:
            if i < len(w1) and w1[i] == c:
                i += 1
        return i == len(w1)
        
    A.sort(key = len, reverse = True)
    for i, word1 in enumerate(A):
        if all(not subseq(word1, word2) 
                for j, word2 in enumerate(A) if i != j):
            return len(word1)
    return -1
    

  • 13

    Mine is similar:

    def findLUSlength(self, strs):
        def issubsequence(s, t):
            t = iter(t)
            return all(c in t for c in s)
        for s in sorted(strs, key=len, reverse=True):
            if sum(issubsequence(s, t) for t in strs) == 1:
                return len(s)
        return -1

  • 3

    My AC solution is a little more efficient (or complicated).

    def findLUSlength(self, strs):
            c = collections.Counter(strs)
    
            def isSub(s1, s2):
                it = iter(s2)
                return all(i in it for i in s1)
            
            for s1 in sorted([str for str in c if c[str] == 1], key=len, reverse=True):
                if sum(isSub(s1, s2) for s2 in strs) == 1:
                    return len(s1)
            return -1
    
    

    Another 1-line soluiton:

    return max([len(s1) for s1 in strs if sum(all(c in it for c in s1) for it in map(iter, strs)) == 1] or [-1])

  • 1

    Similar idea but I only check up to the same length as the "pivot" string. Since the array is ordered descending in length if we hit a string of shorter length before finding a subsequence match then we can return the pivot string right away as all shorter strings cannot be a subsequence of the pivot string.

        def findLUSlength(self, strs):
            def isSub(s,t):
                itr = iter(t)
                return len(s) <= len(t) and all(c in itr for c in s)
                
            strs.sort(key = lambda x: len(x), reverse = True)
            for i in range(len(strs)):
                for j in range(len(strs)):
                    if i != j and isSub(strs[i], strs[j]): break
                    if len(strs[j]) < len(strs[i]) or j == len(strs)-1: return len(strs[i]) 
            return -1
    

  • 9
    C

    @awice Nice solution! I took your idea and wrote it in java

    public int findLUSlength(String[] strs) {
            int len = strs.length;
            
            // reverse sorting array with length 
            Arrays.sort(strs, new Comparator<String>() {
                public int compare(String s1, String s2) {
                    return s2.length() - s1.length();
                }
            });
            
            for(int i=0; i<len; i++){
                int missMatchCount = strs.length - 1;
                for(int j=0; j<len; j++){
                    if(i != j && !isSubSequence(strs[i], strs[j])){
                        missMatchCount --;
                    }
                }
                
                // strs[i] is not a sub sequence of any other entry
                if(missMatchCount == 0){
                    return strs[i].length();
                }
            }
            
            return -1;
        }
        
        private boolean isSubSequence(String s1, String s2){
            int idx = 0;
            for(char ch : s2.toCharArray()){
                if(idx < s1.length() && ch == s1.charAt(idx)){
                    idx++;
                }
            }
            
            return idx == s1.length();
        }
    

  • 0
    K
    This post is deleted!

  • 0
    K

    @awice How can u make the logic so simple and clear?


  • 5
    W

    @chiranjeeb2

    I do not think it is necessary to check all other strings when you already find a string is subSequence of the current one.

      public int findLUSlength(String[] strs) {
        Arrays.sort(strs, (s1, s2) -> s2.length() - s1.length());
        A: for (int i = 0, j; i < strs.length; i++) {
          for (j = 0; j < strs.length; j++)
            if (i != j && isSubSequence(strs[i], strs[j])) continue A;
          return strs[i].length();
        }
        return -1;
      }
    
      private boolean isSubSequence(String s1, String s2) {
        int idx1 = 0, idx2 = 0;
        while (idx1 < s1.length() && idx2 < s2.length())
          if (s1.charAt(idx1) == s2.charAt(idx2++)) idx1++;
        return idx1 == s1.length();
      }

  • 2

    @chiranjeeb2 Another Java version solution. Thanks for sharing!

        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;
        }
    

  • 0
    L

    @wit
    Your code gave a wrong result for the following test case:
    ["aabbcc", "aabbcc","c","e","aabbcd"].
    Output:
    1
    Expected:
    6

    The reason is:
    Arrays.sort(strs, Comparator.comparingInt(s -> s.length())) gives a natural ordering (increased order in terms of length), rather than a decreased order in length.


  • 0
    W

    @Longji

    Thank you very much

    I've already updated my code


  • 0
    L

    @StefanPochmann Wow this is genius. Thank you


  • 0
    M

    That's very clear and concise!

    I'd like to suggest a possible improvement: to separate the duplicates before sorting the list.

    As before the list of unique entries is sorted in descending order, but now we neither need to compare the strings in the list, nor need to consider any duplicate, which can be eliminated quickly using dictionary.

    i.e. We only need to consider if str1 is a substring of str2, for all unique str1 and for all duplicates str2.
    The program should work fast when there are lots of duplicates (few unique strings to traverse) and when there are very little duplicates (few strings to compare)

    btw please forgive me for the non-pythonic coding style in the issub function

    def findLUSlength(self, strs):
        d={}
        for word in strs:
            if word in d:
                d[word]+=1
            else:
                d[word]=1
        t=[word for word in d if d[word]==1]
        t2=[word for word in d if d[word]>1]
        
        def issub(shortword,longword):
            if len(shortword)>=len(longword):
                return shortword==longword
            i,j=0,0
            while i<len(shortword) and j<len(longword):
                while shortword[i]!=longword[j]:
                    j+=1
                    if j==len(longword):
                        break
                else:
                    i+=1
                    j+=1
            return i==len(shortword)
                
        for word in sorted(t,key=lambda x:-len(x)):
            if any (issub(word,w2) for w2 in t2):
                continue
            return len(word)
        return -1
    

  • 0

    @lee215 why need it = iter(s1) in isSub() function?


  • 0

    @0x0101
    If not, it will create a new iter(s1) iteration every time. In my case, I want to traverse the same one.


  • 2
    M

    Similar idea but more explanation to help understand why the string itself is enough for the result.

    Analysis about the problem:

    1. longest string is not subsequence of shorter string. The condition that longest string is not result is that it occurs multiple times in the list, which makes any of its substring is not an option for result;
    2. When above conditons happens, we search for the next longest string, and make sure it's not substring of the longer string and also not occurs multiple times in the list.

    Here is my solution:

    public class Solution {

    public int findLUSlength(String[] strs) {
        if(strs == null || strs.length == 0)
            return -1;
        Arrays.sort(strs, new Comparator<String>(){
            public int compare(String s1, String s2){ 
                return s2.length() - s1.length();
            }
        });
    
        for(int i = 0; i < strs.length; i++){
            boolean valid = true;
            for(int j = 0; j < strs.length; j++){
                if(i != j && strs[j].length() >= strs[i].length()){
                    if(subsequence(strs[j], strs[i])) 
                        valid = false;
                }
            }
            if(valid)
                return strs[i].length();
        }
        
        return -1;
    }
    
    public boolean subsequence(String str, String sub){
        int index = 0;
        for(char c : str.toCharArray()){
            if(index < sub.length() && c == sub.charAt(index))
                index++;
        }
        return index == sub.length();
    }
    

    }


  • 0
    S

    If I test the code for a testcase of ["cc, "baab, "baab", "bcc"] the leetcode expects the answer to be 3 but I think the answer should be -1, someone please calrify! and correct me if I am wrong. Thanks in advance!


  • 0
    D

    @StefanPochmann can you explain (c in t for c in s)? looks like each loop it's checking if c from s1 is in a chr from s2, I printed out next(t) for c in s, but I guess it's not working like that.


  • 0

    @donata001 For every character in s, it checks whether that character also appears in (the remainder of) t.


  • 0
    Y
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.