[2022-06-27]522. 最长特殊序列 II👋数组👋哈希表👋双指针👋字符串👋排序

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/longest-uncommon-subsequence-ii

难度: Medium
标签: 数组 哈希表 双指针 字符串 排序

[dreamjean]

522. 最长特殊序列 II

Description

Difficulty: 中等

Related Topics: 数组, 哈希表, 双指针, 字符串, 排序

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

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

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

• 例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"a<u>e</u>b<u>d</u>c"中的下划线字符来得到 "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] 只包含小写英文字母

Solution

思路：

• 如果存在这样的特殊序列，那么它一定是某个给定的字符串。
• 检查每个字符串是否是其他字符串的子序列。
  • 如果不是，则它是一个特殊序列。最后返回长度最大的特殊序列。
  • 如果不存在特殊序列，返回 -1。

Language: JavaScript

/**
 * @param {string[]} strs
 * @return {number}
 */
var findLUSlength = function(strs) {
    strs.sort((a, b) => b.length - a.length);  //按长度递减排序
    const n = strs.length;

    for (let i = 0; i < n; i++) {
        let isUncommon = true;
        for (let j = 0; j < n; j++) {
            if (i === j) continue;

            if (isSubSequece(strs[i], strs[j])) {   // 检查当前字符串是否是其他字符串的子序列
                isUncommon = false;  
                break;
            }
        }

        if (isUncommon) return strs[i].length;  // 因为已经长度递减排序，因此返回当前字符串的长度
    }

    return -1;
};

const isSubSequece = (str1, str2) => 
    [...str2].reduce((pos, str) => str1[pos] === str ? pos + 1 : pos, 0) === str1.length;