?LeetCode刷題實(shí)戰(zhàn)522：最長特殊序列 II
Given an array of strings strs, return the length of the longest uncommon subsequence between them. If the longest uncommon subsequence does not exist, return -1.
An uncommon subsequence between an array of strings is a string that is a subsequence of one string but not the others.
A subsequence of a string s is a string that can be obtained after deleting any number of characters from s.
For example, "abc" is a subsequence of "aebdc" because you can delete the underlined characters in "aebdc" to get "abc". Other subsequences of "aebdc" include "aebdc", "aeb", and "" (empty string).
示例? ? ? ? ? ? ? ? ? ? ? ? ?
示例：
輸入: "aba", "cdc", "eae"
輸出: 3
提示：
所有給定的字符串長度不會(huì)超過 10?。
給定字符串列表的長度將在 [2, 50?] 之間。
解題
class?Solution?{
public:
????bool?checkSubSeq(string?a, string?b)?{ // 判斷字符串a(chǎn)是否是字符串b的子序列
????????for(int?i = 0, j = 0; i < a.size(); ++i, ++j) {
????????????while(j < b.size() && a[i] != b[j]) {
????????????????++j;
????????????}
????????????if(j == b.size()) { // 如果b走到最后也沒有和a匹配完，那么a不是b的子序列
????????????????return?false;
????????????}
????????}
????????return?true;
????}
????int?findLUSlength(vector<string>& strs)?{
????????sort(strs.begin(), strs.end(), [&](string?a, string?b) { // 將字符串?dāng)?shù)組按照字符串長度從大到小排序
????????????if(a.size() != b.size()) {
????????????????return?a.size() > b.size();
????????????}
????????????return?a < b;
????????});
????????for(int?i = 0; i < strs.size(); ++i) { // 按照字符串長度從大到小枚舉所有的字符串
????????????bool?flag = true; // flag表示當(dāng)前字符串是否是一個(gè)特殊序列
????????????if(i + 1?< strs.size() && strs[i] == strs[i + 1]) { // 如果存在和這個(gè)字符串相同的字符串，則這個(gè)字符串不是特殊序列
????????????????flag = false;
????????????????continue;
????????????}
????????????for(int?j = 0; j < i; ++j) { // 枚舉所有長度比當(dāng)前字符串大的字符串，判斷當(dāng)前字符串是否是其他字符串的子序列
????????????????if(checkSubSeq(strs[i], strs[j]) == true) {
????????????????????flag = false;
????????????????}
????????????}
????????????if(flag == true) { // 找到了一個(gè)特殊序列，它的長度就是答案
????????????????return?strs[i].size();
????????????}
????????}
????????return?-1;
????}
};