[LeetCode] 984. String Without AAA or BBB 不含AAA或BBB的字符串
Given two integers a
and b
, return any string s
such that:
s
has lengtha + b
and contains exactlya
'a'
letters, and exactlyb
'b'
letters,- The substring
'aaa'
does not occur ins
, and - The substring
'bbb'
does not occur ins
.
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 givena
andb
.
这道题给了两个正数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
相关文章
- Leetcode 之Longest Palindromic Substring(30)
- Java实现 LeetCode 53 最大子序和
- 每日一道 LeetCode (12):最大子序和
- LeetCode:151_Reverse Words in a String | 字符串中单词的逆反 | Medium
- [LeetCode] Reverse Vowels of a String
- [LeetCode] Isomorphic Strings
- TypeScript里string和String,真不是仅仅是大小写的区别
- LeetCode【8】. String to Integer (atoi) --java实现
- C# string.Format 和 String.Format 的区别
- Leetcode 729. 我的日程安排表 I(牛逼,已解决)
- leetcode 387. First Unique Character in a String
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
- 【LeetCode】剑指offerII118多余的边