522.最长特殊序列II

链接：522.最长特殊序列II
难度：Medium
标签：数组、哈希表、双指针、字符串、排序
简介：给定字符串列表 strs ，返回其中 最长的特殊序列 。如果最长特殊序列不存在，返回 -1 。

题解 1 - cpp

• 编辑时间：2022-06-27
• 执行用时：4ms
• 内存消耗：8MB
• 编程语言：cpp
• 解法介绍：对于每个字符串，查找是否有父串。

class Solution {
   public:
    int findLUSlength(vector<string> &strs) {
        int ans = -1, n = strs.size();
        for (int i = 0; i < n; i++) {
            string s1 = strs[i];
            bool check = true;
            for (int j = 0; j < n; j++) {
                if (i != j && isSubStr(s1, strs[j])) {
                    check = false;
                    break;
                }
            }
            if (check) ans = max(ans, (int)s1.size());
        }
        return ans;
    }
    bool isSubStr(const string &s1, const string &s2) {
        int i1 = 0, i2 = 0, n1 = s1.size(), n2 = s2.size();
        for (; i1 < n1 && i2 < n2; i2++)
            if (s1[i1] == s2[i2]) i1++;
        return i1 == n1;
    }
};

题解 2 - python

• 编辑时间：2024-06-17
• 执行用时：38ms
• 内存消耗：16.28MB
• 编程语言：python
• 解法介绍：枚举。

class Solution:
    def findLUSlength(self, strs: List[str]) -> int:
        map = Counter(strs)
        strs.sort(key = lambda s: -len(s))
        for i in range(len(strs)):
            s = strs[i]
            if map[s] > 1: continue
            need_continue = False
            for j in range(i):
                i1 = 0
                for c in strs[j]:
                    if s[i1] == c:
                        i1 += 1
                    if i1 == len(s):
                        break
                if i1 == len(s):
                    need_continue = True
                    break
            if need_continue: continue
            return len(s)
        return -1