郑州400建站网站建设,常州低价网站建设公司,广州分享网站建设,网站做次级页面力扣题-12.29
[力扣刷题攻略] Re#xff1a;从零开始的力扣刷题生活
力扣题1#xff1a;522. 最长特殊序列 II
解题思想#xff1a;首先将字符串列表按长度进行降序#xff0c;然后对每个字符串进行判断是否是独有的子序列#xff0c;因为短的字串可能是长的字串的子序…力扣题-12.29
[力扣刷题攻略] Re从零开始的力扣刷题生活
力扣题1522. 最长特殊序列 II
解题思想首先将字符串列表按长度进行降序然后对每个字符串进行判断是否是独有的子序列因为短的字串可能是长的字串的子序列但是长的字串肯定是短字串的独有的子序列通过这个条件进行判断。 class Solution(object):def findLUSlength(self, strs)::type strs: List[str]:rtype: intstrs.sort(keylen,reverseTrue)for i in range(0,len(strs)):if not self.isSubSeqOfAnother(strs,i):return len(strs[i])return -1## 检查给定索引idx处的字符串是否是列表中任何其他字符串的子序列。def isSubSeqOfAnother(self,strs,idx):for i in range(0,len(strs)):if iidx:continue## 判断到小于时之后的可以不用判断了if len(strs[i])len(strs[idx]):break## 判断是否是子序列if self.isSubSeq(strs[idx],strs[i]):return Truereturn False## 判断s1是否为s2的子序列def isSubSeq(self,s1,s2):p1,p20,0while p1len(s1) and p2len(s2):while p2len(s2) and s2[p2]!s1[p1]:p21if p2len(s2):p11p21return p1len(s1)class Solution {
public:int findLUSlength(vectorstring strs) {std::sort(strs.begin(), strs.end(), [](const std::string a, const std::string b) {return a.length() b.length();});for (int i 0; i strs.size(); i) {if (!isSubSeqOfAnother(strs, i)) {return strs[i].length();}}return -1;}bool isSubSeqOfAnother(vectorstring strs,int idx){for(int i0;istrs.size();i){if(i idx){continue;}if(strs[i].length()strs[idx].length()){break;}if(isSubSeq(strs[idx],strs[i])){return true;}}return false;}bool isSubSeq(string s1,string s2){int p1 0, p2 0;while(p1s1.length() p2s2.length()){while(p2s2.length() s2[p2]!s1[p1]){p2;}if(p2s2.length()){p1;}p2;}return p1s1.length();}};
