984. String Without AAA or BBB

Given two integers a and b, return any string s such that:

  • s has length a + b and contains exactly a 'a' letters, and exactly b 'b' letters,
  • The substring 'aaa' does not occur in s, and
  • The substring 'bbb' does not occur in s.

Example 1:

Input: a = 1, b = 2
Output: "abb"
Explanation: "abb", "bab" and "bba" are all correct answers.

Example 2:

Input: a = 4, b = 1
Output: "aabaa"

Constraints:

  • 0 <= a, b <= 100
  • It is guaranteed such an s exists for the given a and b.

这道题给了两个正数a和b,让返回一个长度为 a+b 的字符串,且只由字符a和b组成,要求不能有三个连着的a或b出现,题目说了对于给定的a和b,一定会有正确的解,让返回一种正确的形式就可以了。题目中给了两个例子来帮助理解,可以发现,a和b的大小关系并不确定,无非也就三种,大于等于和小于,最简单的是相等的时候,直接交替排列即可,虽说可能也存在其他合理的排法,但是没有必要,只要返回的是合理的就行了。接下来就要看不等的情况,比较极端的情况就是a和b中有一个为0,这样直接返回另一个字符组成的字符串就行了,另一个字符的个数也不会超过两个,因为题目中限定了一定有合理的解。如果a和b都不为0,且不等的时候怎么办,比如a大于b时,那么此时可以用两个a,加一个b,尽量让a和b往相等的方向靠拢,则此时对 a-2 和 b-1 调用递归即可,同理,若b大于a,那么此时可以用两个b,加一个a,也尽量让a和b往相等的方向靠拢,则此时对 a-1 和 b-2 调用递归即可,参见代码如下:

解法一:

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        if (a == 0) return string(b, 'b');
        if (b == 0) return string(a, 'a');
        if (a == b) return "ab" + strWithout3a3b(a - 1, b - 1);
        if (a > b) return "aab" + strWithout3a3b(a - 2, b - 1);
        return "bba" + strWithout3a3b(a - 1, b - 2);
    }
};

当然不想用递归也行,迭代的解法稍微长一些,用个 while 循环,只要a和b中有一个为0了就停止,若a大于b,加上 aab,然后a自减1,若b大于a,则加上 bba,然后b自减1,若a和b相等,则加上 ab,之后a和b分别均减1。循环退出后,若a和b还有值,还得加到结果 res,参见代码如下:

解法二:

class Solution {
public:
    string strWithout3a3b(int a, int b) {
        string res;
        while (a && b) {
            if (a > b) {
                res += "aab";
                --a;
            } else if (b > a) {
                res += "bba";
                --b;
            } else {
                res += "ab";
            }
            --a; --b;
        }
        res += string(a, 'a');
        res += string(b, 'b');
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/984

参考资料:

https://leetcode.com/problems/string-without-aaa-or-bbb/

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226740/Clean-C%2B%2Bpython-solution

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/227038/C%2B%2B-short-and-simple-solution

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226649/JavaC%2B%2B-(and-Python)-simple-greedy

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation