【题目链接】:https://leetcode.com/contest/leetcode-weekly-contest-26/problems/longest-uncommon-subsequence-ii/

【题意】



字符串变成多个了;

(不止两个)

让你求最长不公共子序列

【题解】



因为最大长度为10;

所以把每个长度有哪些字符串记录下来;

然后从字符串长度由大到小枚举len;

假设这个答案序列为len长度的某个字符串;

然后看看len长度的字符串有没有和它一样的字符串(即出现两次及以上)

有的话不行,找另外一个长度为len的字符串;

否则

再看看这个字符串是不是长度比len长的字符串的子串；

如果不是的话;

就表示找到了;

直接输出len;

否则继续找长度为len的另外的字符串;

判断一个字符串是不是另外一个字符串的子串其实很简单的；

O(l1+l2)就能判断出来;



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 250;

vector <string> v[12];

bool is(string a, string b)

{

    int len1 = a.size(), len2 = b.size();

    int i = 0, j = 0;

    rep1(j,0,len2-1)

        if (b[j] == a[i])

        {

            i++;

            if (i == len1)

                return true;

        }

    return false;

}

class Solution {

public:

    int findLUSlength(vector<string>& strs) {

        int n = strs.size();

        rep1(i, 0, 10)

            v[i].clear();

        rep1(i, 0, n-1)

        {

            int d = strs[i].size();

            v[d].ps(strs[i]);

        }

        rep2(i, 10, 0)

        {

            int len = v[i].size();

            rep1(j, 0, len - 1)

            {

                bool ok = true;

                rep1(k,0,len-1)

                    if (k != j && v[i][j] == v[i][k])

                    {

                        ok = false;

                        break;

                    }

                if (!ok) continue;

                //看看是不是更长串的子串

                rep1(k, i + 1, 10)

                {

                    int len2 = v[k].size();

                    rep1(kk, 0, len2 - 1)

                    {

                        if (is(v[i][j], v[k][kk]))

                        {

                            ok = false;

                            break;

                        }

                    }

                    if (!ok) break;

                }

                if (ok)

                    return i;

            }

        }

        return -1;

    }

};