​LeetCode刷题实战522:最长特殊序列 II

程序IT圈

共 2836字,需浏览 6分钟

 ·

2022-02-12 06:16

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 最长特殊序列 II,我们先来看题面:
https://leetcode-cn.com/problems/longest-uncommon-subsequence-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).


给定字符串列表,你需要从它们中找出最长的特殊序列。最长特殊序列定义如下:该序列为某字符串独有的最长子序列(即不能是其他字符串的子序列)。

子序列可以通过删去字符串中的某些字符实现,但不能改变剩余字符的相对顺序。空序列为所有字符串的子序列,任何字符串为其自身的子序列。

输入将是一个字符串列表,输出是最长特殊序列的长度。如果最长特殊序列不存在,返回 -1 。

示例                         

示例:
输入: "aba", "cdc", "eae"
输出: 3

提示:
所有给定的字符串长度不会超过 10 。
给定字符串列表的长度将在 [2, 50 ] 之间。


解题

https://www.cnblogs.com/linrj/p/13972685.html

可以将字符串数组按照长度从大到小进行排序,然后从前往后遍历,找到第一个特殊序列,这个特殊序列的长度就是答案,如果遍历完数组,都没有找到特殊序列,这返回-1。

特殊序列的判断方法如下:
(1)如果这个字符串存在和它相同的字符串(排序后这两个字符串是相邻的),则这个字符串不是特殊序列。

(2)从最开始(长度最长的)字符串枚举到这个字符串之前的字符串(也就是枚举所有长度比当前字符串大的字符串),判断当前这个字符串是不是其他字符串的子序列,如果是,则它不是特殊序列;如果不是,则当前这个字符串的长度就是最长特殊序列的长度。

代码如下:

class Solution {
public:
    bool checkSubSeq(string a, string b) { // 判断字符串a是否是字符串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) { // 将字符串数组按照字符串长度从大到小排序
            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表示当前字符串是否是一个特殊序列
            if(i + 1 < strs.size() && strs[i] == strs[i + 1]) { // 如果存在和这个字符串相同的字符串,则这个字符串不是特殊序列
                flag = false;
                continue;
            }
            for(int j = 0; j < i; ++j) { // 枚举所有长度比当前字符串大的字符串,判断当前字符串是否是其他字符串的子序列
                if(checkSubSeq(strs[i], strs[j]) == true) {
                    flag = false;
                }
            }
            if(flag == true) { // 找到了一个特殊序列,它的长度就是答案
                return strs[i].size();
            }
        }
        return -1;
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:
LeetCode1-520题汇总,希望对你有点帮助!
LeetCode刷题实战521: 最长特殊序列 Ⅰ

浏览 24
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报