522. 最长特殊序列

Leetcode题目链接: https://leetcode.cn/problems/longest-uncommon-subsequence-ii/

1. 解题思路:

1. 最长特殊序列 显然是数组中某个字符串而非其子序列: 试想如果结果是某个子序列, 那么该子序列所属的字符串也必然是更大的结果(该字符串也必然不是任何其他字符串的子序列!), 因此自相矛盾, 该题的结果必然直接是数组中某个字符串.
2. 题目可以转换为: 找到一个数组中最长且不为其他字符串子序列的元素.

1.1 朴素解法:

class Solution {
public:
    int findLUSlength(const vector<string>& strs) {

        int arrLen = strs.size();
        int ans = -1;
        for (int i = 0; i < arrLen; i++) {
            int signedSizeI = int(strs[i].size()); 
            if (ans > signedSizeI) continue;
            int j = 0;
            for (; j < arrLen; j++) {
                if (j >= arrLen) break;
                if (i == j) continue;
                int signedSizeJ = int(strs[j].size());
                int permission = signedSizeI > signedSizeJ;
                if (! permission && this->isSub(strs[i], strs[j])) {
                    break;
                }
            }
            if (j >= arrLen && ans < signedSizeI) {
                ans = signedSizeI;
            }
        }
        return ans;
    }

private:
    int isSub(const string& a, const string& b) {
        int lengthA = a.length(), lengthB = b.length();
        int i = 0, j = 0;
        while(i < lengthA && j < lengthB) {
            if (a[i] == b[j++]) {
                i++;
            }
        }
        return i == lengthA;
    }
};

1.2 优化1: 预处理

由于存在双层循环, 因此我们想尽可能降低内存循环复杂度

考虑到, 如果一个A长度大于B, 那么A必然不为B的子序列, 那么可以对数组做一个预处理, 将数组逆序排列, 就可以减少一些判断长度操作 (当然, 从小到大排也行, 两者是否会产生区别呢?)

int findLUSlength(vector<string>& strs) {
    sort(strs.begin(), strs.end(), [](const string& a, const string& b){
        return a.length() > b.length();
    });

    int arrLen = strs.size();
    int ans = -1;
    for (int i = 0; i < arrLen; i++) {
        int signedSizeI = int(strs[i].size()); 
        if (ans > signedSizeI) continue;
        int j = 0;
        for (; j < arrLen; j++) {
            if (j >= arrLen) break;
            if (i == j) continue;
            int signedSizeJ = int(strs[j].size());
            int permission = signedSizeI > signedSizeJ;
            if (! permission && this->isSub(strs[i], strs[j])) {
                break;
            } else if (permission) {
                j = arrLen - 1;
            }
        }
        if (j >= arrLen && ans < signedSizeI) {
            ans = signedSizeI;
        }
    }
    return ans;
}

1.3 优化2: 迭代步数

考虑到字符串长度对子序列判断的影响, 在进行双层循环时, 我们完全只需要对j向更长字符串进行遍历即可~

但这样会遇到一个新问题: 如果有长度相同或者甚至完全一样的字符串, 该如何处理呢?

1. 如果预处理时是从大到小排列, 只需要两层循环都逆序即可(如果是正常的从小到大预处理, 则不必考虑这一点)
2. 如果有完全一样的字符串, 处理方式也有一些改变: 如果a是b的子串,j不能直接跳过了, 要将后续所有相同长度的字符串都遍历, 并使用一个集合记录完全相同的字符串(这些字符串必然互为子串, 不能考虑了, 遇到直接跳过). 这样做可以避免出现奇数个相同字符串的问题(且该类字符串无父字符串)

#include<set>
using std::set;

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

        set<int> invalid;
        int arrLen = strs.size();
        int ans = -1;
        for (int i = arrLen - 1; i >= 0; i--) {
            if (invalid.count(i) == 1) continue;
            int signedSizeI = int(strs[i].size()); 
            if (ans > signedSizeI) continue;
            int j = i - 1;
            for (; j >= 0; j--) {
                int signedSizeJ = int(strs[j].size());
                if (j < 0) break;
                if (i == j) continue;
                if (this->isSub(strs[i], strs[j])) {
                    if(invalid.count(i) == 0) invalid.insert(i);
                    if (signedSizeI == signedSizeJ) {
                        if (this->isSub(strs[j], strs[i])){
                            invalid.insert(j);
                        }
                    } else {
                        break;
                    }
                }
            }
            if (invalid.count(i) == 0 && j < 0 && ans < signedSizeI) {
                ans = signedSizeI;
            }
        }
        return ans;
    }

private:
    int isSub(const string& a, const string& b) {
        int lengthA = a.length(), lengthB = b.length();
        int i = 0, j = 0;
        while(i < lengthA && j < lengthB) {
            if (a[i] == b[j++]) {
                i++;
            }
        }
        return i == lengthA;
    }
};