522. Longest special sequence II

522. The longest special sequence II

subject

Given string list strs , Return to it The longest special sequence The length of . 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 Subsequence You can delete the string 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 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

Related Topics

Array

Hashtable

Double pointer

character string

Sort

Answer key

$$whenbetweencomplexmiscellaneousdegree：O(n^2\cdot l),ItsinnyesCountGroup\text{strs}OfLongdegree,lyeswordoperatorstrandOfflatallLongdegree.$$

class Solution {
    
    public int findLUSlength(String[] strs) {
    
        int n = strs.length;
        int ans = -1;
        for(int i = 0;i < n;i++){
    
            boolean check = true;
            for(int j = 0;j < n;j++){
    
                if(i != j && isSubseq(strs[i],strs[j])){
    
                    check = false;
                    break;
                }
            }
            if(check)
                ans = Math.max(ans, strs[i].length());
        }
        return ans;
    }
    public boolean isSubseq(String s,String t){
    
        int ptS = 0,ptT = 0;
        while (ptS < s.length() && ptT < t.length()){
    
            if(s.charAt(ptS) == t.charAt(ptT))
                ptS++;
            ptT++;
        }
        return ptS == s.length();
    }
}

Solution ideas

The granularity of the operation is str[i] Instead of str[i] The subsequences of

1. If str[i] A certain subsequence of the question is “ Special sequence ”, Add characters to it , So that the original string str[i], It shall also meet the requirements . Compared with str[i] Because the string length is longer , And win .
2. So just compare each str[i], Whether it is other str[j] Subsequence of
3. If more than one strp[i] accord with “ Special sequence ” requirement , Compare and take the longer one as the result

Application of double pointer

1. Compare strings in pairs

           for(int i = 0;i < n;i++){
         	// Every string from beginning to end :str[i]
               boolean check = true;	// By default, it conforms to “ Special sequence ” requirement 
               for(int j = 0;j < n;j++){
         	// Then traverse to get “ the other one ” character string :str[j]
                   if(i != j && isSubseq(strs[i],strs[j])){
         	// If they are different and have a substring relationship 
                       check = false;	// determine str[i] Not meeting the conditions 
                       break;
                   }
               }
               if(check)				// If the conditions are met , Compare and take the longest as the result 
                   ans = Math.max(ans, strs[i].length());
           }
   

2. Compare whether two strings have a substring relationship

       public boolean isSubseq(String s,String t){
         	// Judge  s  Is it  t  The string of 
           int ptS = 0,ptT = 0;	// Point to the beginning of two strings respectively 
           while (ptS < s.length() && ptT < t.length()){
         	// Stop after traversing any string 
               if(s.charAt(ptS) == t.charAt(ptT))	// The same thing  s++, t++
                   ptS++;
               ptT++;					// The difference is  t++
           }
           return ptS == s.length(); 	// If it is a substring , You should complete the traversal  s 
       }