1. 題目

給定字符串列表，你需要從它們中找出最長的特殊序列。
最長特殊序列定義如下：該序列為某字符串獨有的最長子序列（即不能是其他字符串的子序列）。

子序列可以通過刪去字符串中的某些字符實現(xiàn)，但不能改變剩余字符的相對順序。空序列為所有字符串的子序列，任何字符串為其自身的子序列。

輸入將是一個字符串列表，輸出是最長特殊序列的長度。如果最長特殊序列不存在，返回 -1 。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-uncommon-subsequence-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 類似題目：LeetCode 521. 最長特殊序列 Ⅰ

題目意思是，找一個最長的字符，且這個字符不能從別人那里順次挑出（別人的子序，可以隔著字符，不是子串，子串必須連續(xù)）
所以有重復(fù)的字符串不是答案，從不重復(fù)的字符串中，從最長的開始找（先排序），檢查這個最長的字符是不是原字符串集合中的字符串的子序。

class Solution { public:int findLUSlength(vector<string>& strs) {sort(strs.begin(), strs.end(),[&](auto a, auto b){return a.size() > b.size();//按長度排序});map<string,int> m;for(auto it = strs.begin(); it != strs.end(); ++it)m[*it]++;vector<string> uniq;for(auto it = m.begin(); it != m.end(); ++it){if(it->second == 1)//次數(shù)一次的收集起來uniq.push_back(it->first);}sort(uniq.begin(), uniq.end(),[&](auto a, auto b){return a.size() > b.size();//按長度排序});for(auto it = uniq.begin(); it != uniq.end(); ++it){if(!subSeq(strs,*it))return it->size();}return -1;}bool subSeq(vector<string> &strs, string& s){int len = s.size(), i, j;bool flag;for(auto it = strs.begin(); *it != s; ++it){ //str是從長到短的flag = true;for(i = 0,j = 0; i < len; ++i,++j){while(j < it->size() && (*it)[j] != s[i])j++;//長字符串中的字符不等if(j == it->size() && i < len){flag = false;//不是子序break;}else if(i == len-1 && j <= it->size()){flag = true;break;}}if(flag)//是子序break;}return flag;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 522. 最长特殊序列 II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。