Longest Uncommon Subsequence II problem solution

by

In this Leetcode Longest Uncommon Subsequence II problem solution we have 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).

Longest Uncommon Subsequence II problem solution

Problem solution in Python.

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

Problem solution in Java.

class Solution {
    public int findLUSlength(String[] strs) {
        int res=-1, n=strs.length;
        for (int i=0; i<n; i++){
            if (strs[i].length()<res) continue;
            int j=-1;
            while(++j<n) if (i!=j && isSubsequence(strs[i], strs[j])) break;
            if (j==n) res=Math.max(res, strs[i].length());
        }
        return res;
    }
    public boolean isSubsequence(String a, String b){
        int i=0, j=0;
        while(i<a.length() && j<b.length()) if (a.charAt(i)==b.charAt(j++)) i++;
        return i==a.length();
    }
}

Problem solution in C++.

class Solution {
    static bool comp(string &a, string &b){
        return a.size() > b.size();
    }
    bool same(string &s1, string &s2)
    {
        int n = s1.size(), j = 0;
        for(int i = 0; i < n; i++)
        {
            if(s1[i] == s2[j])
            {
                j++;
                if(j == s2.size())
                    return true;
            }
        }
        return false;
    }
    bool iscommon(vector<string>& strs, string s, int idx)
    {
        int n = strs.size(), m = s.size();
        for(int i = 0; i < n && strs[i].size() >= m; i++)
        {
            if(idx == i) continue;
            if(same(strs[i], s))
                return false;
        }
        return true;
    }
public:
    int findLUSlength(vector<string>& strs) {
        sort(strs.begin(), strs.end(), comp);
        int n = strs.size();
        for(int i = 0; i < n; i++)
        {
            if(iscommon(strs, strs[i], i))
                return strs[i].size();
        }
        return -1;
    }
};

Problem solution in C.

int max(int a,int b)
{
    return a>b?a:b;
}

bool LCS(char* a, char* b) {
        if (strlen(a)<strlen(b)) return false;
        int i = 0;
        for(int k=0;k<strlen(a);k++) {
            if(i < strlen(b) && b[i] == a[k]) i++;
        }
        return i == strlen(b);
}

int findLUSlength(char ** strs, int strsSize){
    int ret=-1,i,j;

    for(i=0;i<strsSize;i++)
    {
        for(j=0;j<strsSize;j++)
        {
            if(i==j)
                continue;
            if(LCS(strs[j],strs[i]))
                break;
        }
        if(j==strsSize)
            ret=max(ret,strlen(strs[i]));
    }
    return ret;
}