Leetcode daily question - 522 Longest special sequence II

subject

Given string list strs , Return to it The longest special sequence . If the longest special sequence does not exist , return -1 .

Special sequence The definition is as follows ： The sequence is a string Unique subsequence （ That is, it cannot be a subsequence of another string ）.

s Of Subsequences can be made by deleting strings s Implementation of some characters in .

• for example ,“abc” yes “aebdc” The subsequence , Because you can delete "aebdc" Use the underscore character in to get “abc”
  .“aebdc" The subsequence of also includes "aebdc”、 “aeb” and “” ( An empty string ).

Example

Example 1：

Input : strs = [“aba”,“cdc”,“eae”]
Output : 3

Example 2:

Input : strs = [“aaa”,“aaa”,“aa”]
Output : -1

Tips :

2 <= strs.length <= 50
1 <= strs[i].length <= 10
strs[i] Only lowercase letters

Ideas

• Meaning of this question ： Find the length of the longest repeatless subsequence
• Here's a way of thinking ： That is, the subsequence of a string is a non repeating subsequence , The string itself is also a non repeating subsequence （ perhaps ： If this string is a subsequence of other strings , Then all subsequences of this string are subsequences of other strings , There is no need to compare subsequences of this string ）
• According to this idea , Just judge whether this string is a subsequence of other strings , If this string is not a subsequence of all other strings , Record length , Finally, find the maximum length

Answer key

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
    	#  Determine whether it is a subsequence 
        def isson(str1, str2):
            i,j = 0, 0
            while i < len(str1) and j < len(str2):
                if str1[i] == str2[j]:
                    i += 1
                    j += 1
                else:
                    j += 1
            return i == len(str1)
        ans = -1
        for i in range(len(strs)):
            judge = True
            for j in range(len(strs)):
                if i == j:
                    continue
                if isson(strs[i], strs[j]):
                    judge = False
                    break
            #  Maximum value of update results 
            if judge:
                ans = max(ans, len(strs[i]))
        return ans