leetcode 522. Longest special sequence II

Title Description

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

analysis

This question is still a little interesting , If you know the nature, you can do it quickly , If you don't know the nature, you can only enumerate by force , Violence enumeration also requires skill , The following uses violent enumeration algorithm and more efficient algorithm to solve this problem .

Method 1

Since the longest special subsequence is required , So let's enumerate all the subsequences , Then judge that the subsequence appears in several strings , Under statistics, the maximum length of subsequences that only appear in a string, that is, special sequences . Each string is no longer than 10, The number of subsequences is 2¹⁰, most 50 Subsequence , The total number of subsequences is just 5w Grade , There is no problem enumerating all the violence .

The first question is , How to enumerate subsequences , Currently, binary representation is used to enumerate , It was also mentioned in the problem solution of the previous week's competition .

vector<string> v(1<<n);
unordered_set<string> us;
for(int k = 0;k < n;k++){
    
	for(int j = 0;j < 1 << k;j++){
    
    	v[j|1<<k] = x[k] + v[j];
        us.insert(v[j|1<<k]);
      }
 }

Add... Bit by bit from low to high 1 To enumerate subsequences , And add subsequences to set Remove the weight inside , Because a subsequence can be repeated in the same string , In order to prevent repeated statistics when counting the occurrence times of subsequences , So go to the next heavy .

Then put it directly into map You can increase the count in the , In the end in map The number of occurrences in 1 A subsequence of is a special sequence , Use their length to update the solution , There is one caveat , When updating the solution res The initial value of -1, If used directly size And -1 Compare , What you get is always size < -1, because STL Container of size（） The return value of the function is unsigned type , Compared with the number with matching type, it will be uniformly converted to unsigned number , and -1 The conversion to unsigned is 11111…, Nature is greater than all size. So we need to put size Turn into int Then compare the types .

The code of violence enumeration is as follows ：

class Solution {
    
public:
    unordered_map<string,int> m;
    int findLUSlength(vector<string>& strs) {
    
        int res = -1;
        for(int i = 0;i < strs.size();i++){
    
            string &x = strs[i];
            int n = x.size();
            vector<string> v(1<<n);
            unordered_set<string> us;
            for(int k = 0;k < n;k++){
    
                for(int j = 0;j < 1 << k;j++){
    
                    v[j|1<<k] = x[k] + v[j];
                    us.insert(v[j|1<<k]);
                }
            }
            for(auto t : us)    m[t]++;
        }
        for(auto &[x,y] : m){
    
            int n = x.size();
            if(y == 1 && n > res)    res = x.size();
        }
        return res;
    }
};

Method 2

When we learn the linear correlation of vectors in Linear Algebra , A property is if two vectors a and b Linearly independent , Then the vector group obtained by increasing their dimensions is also linearly independent . such as (1,0) and (0,1) Linearly independent , Add one dimension to get (1,0,1),(0,1,1) It's also linearly independent . The same is true of this question , If there is a special sequence in a string , That is, a subsequence of a string is not a subsequence of another string , If we increase the length of this subsequence, it will not be a subsequence of other strings , That is to say , If there is a special sequence in a string , Then the string itself is a special sequence .

So we just need to enumerate each string , Determine whether it is a subsequence of other strings . If it is a judgment substring, it can be used directly string Inside find function , To judge the subsequence, you have to use double pointer comparison , It's a little bit easier .

class Solution {
    
public:
    int findLUSlength(vector<string>& strs) {
    
        int res = -1,n = strs.size();
        for(int i = 0;i < n;i++){
    
            string &x = strs[i];
            bool flag = true;
            for(int j = 0;j < n;j++){
    
                if(j == i)  continue;
                string &y = strs[j];
                if(x.size() <= y.size()) {
    
                    int p = 0,q = 0;
                    while(p < x.size() && q < y.size()){
    
                        if(x[p] == y[q])    p++,q++;
                        else    q++;
                    }
                    if(p == x.size()){
    
                        flag = false;
                        break;
                    }   
                }
            }
            if(flag)    res = max(res,(int)x.size());
        }
        return res;
    }
};