中等

问题描述

给定字符串列表 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] 只包含小写英文字母

枚举

枚举数组中的字符串，对比当前字符串 $str1$ 与其他字符串 $str2$，使用两个指针 $p1$ 和 $p2$ 分别指向两个字符串，若指针指向的字符一致，则两个指针同时右移，若不一致，则 $p2$ 右移，最终直到某个字符串遍历完毕，此时若 $p1$ 指向当前字符串 $str1$ 的尾部，则说明当前字符串 $str1$ 是 $str2$ 的子序列，直接进行下个字符串的查找，最终找出长度最长的特殊子序列的长度。

/**
 * @param {string[]} strs
 * @return {number}
 */
var findLUSlength = function (strs) {
  let ans = -1
  const n = strs.length
  loop: for (let i = 0; i < n; i++) {
    const str1 = strs[i]
    for (let j = 0; j < n; j++) {
      if (i === j) continue
      const str2 = strs[j]
      let p1 = 0
      let p2 = 0
      while (p1 < str1.length && p2 < str2.length) {
        if (str1[p1] === str2[p2]) {
          p1++
          p2++
        } else {
          p2++
        }
      }
      if (p1 === str1.length) continue loop
    }
    ans = Math.max(ans, strs[i].length)
  }
  return ans
}

• 时间复杂度：$O(n^2 \times l)$，$n$ 为数组长度，$l$ 为序列平均长度。
• 空间复杂度：$O(1)$