[每日一题] 522.最长特殊序列II

博主： Richard
发布时间：2024 年 06 月 17 日
119 次浏览
暂无评论
1370字数
分类： LeetCode

> https://leetcode.cn/problems/longest-uncommon-subsequence-ii/description/?envType=daily-question&envId=2024-05-02

数据量不大，所以可以直接暴力法，用两个 `for` 循环，从长到短判断每个字符串是否为其他字符串的子序列。

判断是否为子序列的方法可以用双指针。

```c++
class Solution {
public:
    int findLUSlength(std::vector<std::string> &strs) {
        const int n = strs.size();
        std::sort(strs.begin(), strs.end(), [](std::string &a, std::string &b) { return a.length() > b.length(); });

for (int i = 0; i < n; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == j)
                    continue;

if (j == n || strs[i].length() > strs[j].length())
                    return strs[i].length();
                
                if (strs[i].length() == strs[j].length()) {
                    if (strs[i] == strs[j])
                        break;                     
                    else
                        continue;
                }

int first = 0, second = 0;
                while (first < strs[i].length() && second < strs[j].length()) {
                    if (strs[i][first] == strs[j][second])
                        first++;
                    second++;
                }

if (first == strs[i].length())
                    break;
            }
        }
        
        return -1;
    }
};
```

- 时间复杂度：$O(n^2 \cdot l)$ ，其中 $n$ 为数组 `str` 的长度，$l$ 为字符串的平均长度。
- 空间复杂度：$O(logn)$ ，排序需要 $O(logn)$ 的栈空间消耗。

最后修改：2024 年 06 月 17 日