最长特殊序列 II

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

  • 输入: strs = [“aba”,”cdc”,”eae”]

  • 输出: 3

  • 输入: strs = [“aaa”,”aaa”,”aa”]

  • 输出: -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
};