522. 最长特殊序列 II

解题过程

INFO

题目链接给定字符串列表 strs ，返回其中最长的特殊序列的长度。如果最长特殊序列不存在，返回 -1 。特殊序列定义如下：该序列为某字符串独有的子序列（即不能是其他字符串的子序列）。 s 的子序列可以通过删去字符串 s 中的某些字符实现。例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)

javascript

/**
 * @link https://leetcode.cn/problems/longest-uncommon-subsequence-ii/
 * @title 522. 最长特殊序列 II
 * @description 给定字符串列表 strs ，返回其中 最长的特殊序列 的长度。如果最长特殊序列不存在，返回 -1 。

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

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

例如，"abc" 是 "aebdc" 的子序列，因为您可以删除"aebdc"中的下划线字符来得到 "abc" 。"aebdc"的子序列还包括"aebdc"、 "aeb" 和 "" (空字符串)
 * @param {string[]} strs
 * @return {number}
 */
// 解法一
// 思路：
var findLUSlength = function (strs) {
  let map = {}, max = 0, str
  // 哈希表计数 并且寻找最长字符串
  for (let i = strs.length - 1; i >= 0; i--) {
    map[strs[i]] ? map[strs[i]]++ : map[strs[i]] = 1

    if (strs[i].length > max) {
      max = strs[i].length
      str = strs[i]
    }
  }

  // 最长字符串是唯一的
  if (map[str] == 1) {
    return max
  }

  max = -1
  // 双指针比较
  let compare = function (target, origin) {
    let i = 0, j = 0, n = target.length, m = origin.length
    while (i < n && j < m) {
      if (origin[j] == target[i]) j++
      i++
    }
    return j == m
  }

  // 取出哈希表中的唯一的字符串与str（最长的字符串）进行比较 判断是否为它的子串
  for (let key in map) {
    if (map[key] == 1 && !compare(str, key)) {
      max = Math.max(key.length, max)
    }
  }

  return max
};

// const result = findLUSlength(["aba", "cdc", "eae"]) // 3
const result = findLUSlength(["aaa", "aaa", "aa"]) // -1
console.log(result)

522. 最长特殊序列 II

解题过程

解题感受

优质题解

522. 最长特殊序列 II ​

解题过程 ​

解题感受 ​

优质题解 ​

522. 最长特殊序列 II

解题过程

解题感受

优质题解