Medium

题目描述

给定字符串数组 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] 由小写英文字母组成

解题思路

这道题的核心思想是理解什么是"特殊序列”。

首先明确一个重要观察：如果一个字符串在数组中是唯一的（不与其他字符串重复），那么这个字符串本身就是一个特殊序列。因为它是自己的子序列，但不可能是其他不同字符串的子序列。

基于这个观察，我们的解题思路是：

  1. 遍历数组中的每个字符串
  2. 检查该字符串是否与数组中其他字符串重复
  3. 如果不重复，该字符串就是特殊序列，记录其长度
  4. 返回所有特殊序列中的最大长度

更进一步的思考：对于重复的字符串，我们需要检查它们的所有真子序列是否为特殊序列。但实际上，由于数据规模较小（字符串长度≤10，数组长度≤50），我们可以采用暴力方法：

  • 生成每个字符串的所有子序列
  • 检查每个子序列是否只在一个原字符串中出现
  • 找到最长的这样的子序列

不过，基于第一个观察的简化方法在大多数情况下就足够了，因为如果存在唯一字符串，它们的长度通常就是答案。

代码实现

class Solution {
public:
    int findLUSlength(vector<string>& strs) {
        int n = strs.size();
        int maxLen = -1;
        
        // 检查每个字符串是否为特殊序列
        for (int i = 0; i < n; i++) {
            bool isUncommon = true;
            
            // 检查当前字符串是否是其他字符串的子序列
            for (int j = 0; j < n; j++) {
                if (i != j && isSubsequence(strs[i], strs[j])) {
                    isUncommon = false;
                    break;
                }
            }
            
            if (isUncommon) {
                maxLen = max(maxLen, (int)strs[i].length());
            }
        }
        
        return maxLen;
    }
    
private:
    bool isSubsequence(const string& s, const string& t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == s.length();
    }
};

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        def is_subsequence(s, t):
            i = 0
            for char in t:
                if i < len(s) and s[i] == char:
                    i += 1
            return i == len(s)
        
        n = len(strs)
        max_len = -1
        
        # 检查每个字符串是否为特殊序列
        for i in range(n):
            is_uncommon = True
            
            # 检查当前字符串是否是其他字符串的子序列
            for j in range(n):
                if i != j and is_subsequence(strs[i], strs[j]):
                    is_uncommon = False
                    break
            
            if is_uncommon:
                max_len = max(max_len, len(strs[i]))
        
        return max_len

public class Solution {
    public int FindLUSlength(string[] strs) {
        int n = strs.Length;
        int maxLen = -1;
        
        // 检查每个字符串是否为特殊序列
        for (int i = 0; i < n; i++) {
            bool isUncommon = true;
            
            // 检查当前字符串是否是其他字符串的子序列
            for (int j = 0; j < n; j++) {
                if (i != j && IsSubsequence(strs[i], strs[j])) {
                    isUncommon = false;
                    break;
                }
            }
            
            if (isUncommon) {
                maxLen = Math.Max(maxLen, strs[i].Length);
            }
        }
        
        return maxLen;
    }
    
    private bool IsSubsequence(string s, string t) {
        int i = 0, j = 0;
        while (i < s.Length && j < t.Length) {
            if (s[i] == t[j]) {
                i++;
            }
            j++;
        }
        return i == s.Length;
    }
}

/**
 * @param {string[]} strs
 * @return {number}
 */
var findLUSlength = function(strs) {
    function isSubsequence(s, t) {
        let i = 0;
        for (let j = 0; j < t.length && i < s.length; j++) {
            if (s[i] === t[j]) i++;
        }
        return i === s.length;
    }
    
    strs.sort((a, b) => b.length - a.length);
    
    for (let i = 0; i < strs.length; i++) {
        let isUncommon = true;
        for (let j = 0; j < strs.length; j++) {
            if (i !== j && isSubsequence(strs[i], strs[j])) {
                isUncommon = false;
                break;
            }
        }
        if (isUncommon) return strs[i].length;
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n² × m)，其中 n 是字符串数组的长度，m 是字符串的平均长度。需要对每个字符串检查是否为其他字符串的子序列
空间复杂度O(1)，只使用了常数额外空间

相关题目