522. 最长的特殊序列 II

522. 最长的特殊序列 II

题目

给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

特殊序列 定义如下：该序列为某字符串 独有的子序列（即不能是其他字符串的子序列）。

s 的 子序列可以通过删去字符串 s 中的某些字符实现。

• 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 “” (空字符串)。

示例 1：

输入: strs = ["aba","cdc","eae"]
输出: 3

示例 2:

输入: strs = ["aaa","aaa","aa"]
输出: -1

提示:

• 2 <= strs.length <= 50
• 1 <= strs[i].length <= 10
• strs[i] 只包含小写英文字母

Related Topics

数组

哈希表

双指针

字符串

排序

题解

$$时间复杂度：O(n^2\cdot l)，其中n是数组\text{strs}的长度，l是字符串的平均长度。$$

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

解法思路

操作细粒度为 str[i] 而非 str[i]的各子序列

1. 如果str[i]的某子序列为符合题目要求的“特殊序列”，则对其添加字符，以至于成原字符串str[i]，也应满足要求。相比而言str[i]因字符串长度更长，而优胜。
2. 所以只需比较各str[i]，是否为其他str[j]的子序列即可
3. 若多个strp[i]符合“特殊序列”要求，比较取更长者为结果

双指针的应用

1. 两两比较字符串

           for(int i = 0;i < n;i++){
         	//从头到尾的每个字符串:str[i]
               boolean check = true;	//默认它是符合“特殊序列”要求
               for(int j = 0;j < n;j++){
         	//再遍历取得“另一个”字符串:str[j]
                   if(i != j && isSubseq(strs[i],strs[j])){
         	//若两者不同且有子串关系
                       check = false;	//判定str[i]不满足条件
                       break;
                   }
               }
               if(check)				//若满足条件，比较取最长为结果
                   ans = Math.max(ans, strs[i].length());
           }
   

2. 比较两字符串是否有子串关系

       public boolean isSubseq(String s,String t){
         	//判断 s 是否为 t 的子串
           int ptS = 0,ptT = 0;	//分别指向两字符串首
           while (ptS < s.length() && ptT < t.length()){
         	//任一字符串遍历完即停止
               if(s.charAt(ptS) == t.charAt(ptT))	//相同则 s++, t++
                   ptS++;
               ptT++;					//不同则 t++
           }
           return ptS == s.length(); 	//若为子串，则应遍历完 s 
       }