[LeetCode 1763] 最长的美好子字符串 [参考]

文章目录


这是简单题???数据规模后边加3个0直接玩完…

题目链接

https://leetcode-cn.com/problems/longest-nice-substring/
官方题解

题目描述

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中,就称这个字符串 s美好 字符串。比方说,"abABB" 是美好字符串,因为 'A''a' 同时出现了,且 'B''b' 也同时出现了。然而,"abA" 不是美好字符串因为 'b' 出现了,而 'B' 没有出现。

给你一个字符串 s ,请你返回 s 最长的 美好子字符串 。如果有多个答案,请你返回 最早 出现的一个。如果不存在美好子字符串,请你返回一个空字符串。


示例1

输入:s = "YazaAay"
输出:"aAa"
解释:"aAa" 是一个美好字符串,因为这个子串中仅含一种字母,其小写形式 'a' 和大写形式 'A' 也同时出现了。
"aAa" 是最长的美好子字符串。

示例2

输入:s = "Bb"
输出:"Bb" 
解释:"Bb" 是美好字符串,因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。

示例3

输入:s = "c" 
输出:""
解释:没有美好子字符串。

示例4

输入:s = "dDzeE"
输出:"dD"
解释:"dD" 和 "eE" 都是最长美好子字符串。
由于有多个美好子字符串,返回 "dD" ,因为它出现得最早。

提示

  • 1 <= s.length <= 100
  • s 只包含大写和小写英文字母。

题解1

暴力穷举所有的子串,判断每个子串是否是美好字符串。时间复杂度 O ( n 3 ) O(n^3) O(n3), n n n为字符串长度。

代码如下:

class Solution {
public:
    bool isgood(string &s, int l, int r)
    {
        bool appear[200] = {false};
        for(int i=l;i<r;i++)    appear[s[i]] = true;
        for(char c='a';c <= 'z';c++)
        {
            if(appear[c] != appear[c + 'A' - 'a'])  return false;
        }
        return true;
    }
    string longestNiceSubstring(string s) {
        int maxl = -1;
        int leftofmax = -1;
        for(int l=0;l<s.length();l++)
        {
            for(int r=l+1;r<=s.length();r++)
            {
                if(r - l > maxl && isgood(s, l, r))
                {
                    maxl = r - l;
                    leftofmax = l;
                }
            }
        }
        if(maxl != -1)  return s.substr(leftofmax, maxl);
        else return "";
    }
};

实际上,对于小于等于当前最长美好子串长度的子串没必要再验证,因此程序可以优化。

string longestNiceSubstring(string s) {
        int maxl = -1;
        int leftofmax = -1;
        for(int l=0;l<s.length();l++)
        {
            for(int r=l+maxl+1 ;r<=s.length();r++)
            {
                if(isgood(s, l, r))
                {
                    maxl = r - l;
                    leftofmax = l;
                }
            }
        }
        if(maxl != -1)  return s.substr(leftofmax, maxl);
        else return "";
    }

题解2

判断子串是否是美好的方法可以优化:对于一个子串,统计区分大小写和不区分大小写的种类数,如果前者是后者的两倍,那么就是美好字符串,边统计边判断,时间复杂度 O ( n 2 ) O(n^2) O(n2)。

class Solution {
public:
    char lower(char c)
    {
        if (c >= 'A' && c <= 'Z')   return c - 'A' + 'a';
        return c;
    }
    string longestNiceSubstring(string s) {
        int maxl = -1;
        int leftofmax = -1;
        for(int l=0;l<s.length();l++)
        {
            int num1 = 0; // 区分大小写的字母种类
            int num2 = 0; // 不区分大小写的字母种类
            bool appear1[200] = {false};
            bool appear2[200] = {false};
            for(int r=l; r<s.length(); r++)
            {
                if (!appear1[s[r]])
                {
                    num1++;
                    appear1[s[r]] = true;
                }
                if (!appear2[lower(s[r])])
                {
                    num2++;
                    appear2[lower(s[r])] = true;
                }
                if(r - l + 1 > maxl && num1 == num2 * 2)
                {
                    maxl = r - l + 1;
                    leftofmax = l;
                }
            }
        }
        if(maxl != -1)  return s.substr(leftofmax, maxl);
        else return "";
    }
};

因为只有26个英文字母,所以可以数字二进制每一位表示一个英文字母有没有出现,分别统计大写字母和小写字母的出现情况,代码可以写的更简单,时间复杂度 O ( n 2 ) O(n^2) O(n2)。

class Solution {
public:
    string longestNiceSubstring(string s) {
        int maxl = -1;
        int leftofmax = -1;
        for(int l=0;l<s.length();l++)
        {
            int lower = 0; // 小写字母出现情况
            int upper = 0; // 大写字母出现情况
            for(int r=l; r<s.length(); r++)
            {
                if(s[r] >= 'a' && s[r] <= 'z')  lower |= (1 << (s[r] - 'a'));
                else upper |= (1 << (s[r] - 'A'));
                if(r - l + 1 > maxl && lower == upper)
                {
                    maxl = r - l + 1;
                    leftofmax = l;
                }
            }
        }
        if(maxl != -1)  return s.substr(leftofmax, maxl);
        else return "";
    }
};

题解3(参考自官方题解)

利用分治的思想,对于一个字符串,如果它不是美好的,那么其中一定有一些字母在这个字符串中没有大小写同时出现,可以用这些字母把字符串分割成若干子串,再去判断每个子串是不是美好的。看题解说时间复杂度可以达到 O ( n ) O(n) O(n),虽然我不知道为啥。

class Solution {
private:
    int maxl;
    int leftofmax;
public:
    char Lower(char c)
    {
        if(c >= 'a' && c <= 'z')    return c;
        return c - 'A' + 'a';
    }
    void dfs(string &s, int l, int r)
    {
        if(r - l > maxl && l > leftofmax)
        {
            int lower = 0;
            int upper = 0;
            for(int i=l;i<r;i++)
            {
                if(s[i] >= 'a' && s[i] <= 'z')  lower |= (1 << (s[i] - 'a'));
                else upper |= (1 << (s[i] - 'A'));
            }
            if(lower == upper)
            {
                maxl = r - l;
                leftofmax = l;
                return;
            }
            int legal = (lower & upper);
            int p = l;
            while(p < r)
            {
                l = p;
                char lc;
                while(p < r && (legal & (1 << (Lower(s[p]) - 'a'))))    p++;
                dfs(s, l, p);
                p++;
            }
        }
        
    }
    string longestNiceSubstring(string s) {
        maxl = -1;
        leftofmax = -1;
        dfs(s, 0, s.length());
        if(maxl != -1)  return s.substr(leftofmax, maxl);
        else return "";
    }
};
上一篇:Prime Distance


下一篇:Array Destruction