题目
如果一个字符串满足以下条件，则称其为美丽字符串：
- 它由英语小写字母表的前
k个字母组成。 - 它不包含任何长度为 2 或更长的回文子字符串。
给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。
对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。
例如，“abcd” 的字典序比 “abcc” 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c。
示例 1:
输入：s = “abcz”, k = 26
输出：“abda”
解释：字符串 “abda” 既是美丽字符串，又满足字典序大于 “abcz”。可以证明不存在字符串同时满足字典序大于 “abcz”、美丽字符串、字典序小于 “abda” 这三个条件。
示例 2:
输入：s = “dc”, k = 4
输出：“”
解释：可以证明，不存在既是美丽字符串，又字典序大于 “dc” 的字符串。
提示：
- 1 <= n == s.length <= 10^5
- 4 <= k <= 26
- s 是一个美丽字符串
代码
完整代码
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
bool isBeauty(char* s, int len) {
if (len == 0 || len == 1) {
return false;
} else if (len == 2) {
return s[0] != s[1];
}
for (int i = 0; i + 2 < len; i++) {
if (s[i] == s[i + 1] || s[i] == s[i + 2] || s[i + 1] == s[i + 2]) {
return false;
}
}
return true;
}
char* smallestBeautifulString(char* s, int k) {
char alphaBet[] = "abcdefghijklmnopqrstuvwxyz";
int len = strlen(s);
if (len == 1 && s[0] < alphaBet[k-1]) {
s[0]++;
return s;
}
char* result = (char*)calloc(len + 1, sizeof(char));
strcpy(result, s);
while (1) {
for (int i = len - 1; i >= 0; i--) {
if (result[i] < alphaBet[k - 1]) {
result[i]++;
for (int j = i + 1; j < len; j++) {
result[j] = alphaBet[0];
}
if (isBeauty(result, len)) {
return result;
}
break;
} else {
result[i] = alphaBet[0];
}
}
bool allMax = true;
for (int i = 0; i < len; i++) {
if (result[i] != alphaBet[k - 1]) {
allMax = false;
break;
}
}
if (allMax) {
break;
}
}
free(result);
return strdup("");
}
思路分析
这套代码用了模拟的方法。
- 首先初始化一个结果字符串
result，它的初始值为输入字符串s。 - 从字符串的末尾开始，逐个字符尝试将其增加。
- 每次增加一个字符后，检查整个字符串是否仍然是美丽字符串。
- 如果是美丽字符串，则返回该字符串。
- 如果所有字符都尝试过最大值，且仍然找不到合适的字符串，则返回空字符串。
拆解分析
isBeauty函数
bool isBeauty(char* s, int len) {
if (len == 0 || len == 1) {
return false;
} else if (len == 2) {
return s[0] != s[1];
}
for (int i = 0; i + 2 < len; i++) {
if (s[i] == s[i + 1] || s[i] == s[i + 2] || s[i + 1] == s[i + 2]) {
return false;
}
}
return true;
}
isBeauty函数用于检查一个字符串是否为美丽字符串。具体实现为判断字符串中是否存在长度为2或更长的回文子字符串。
- 初始检查与内存分配
char* smallestBeautifulString(char* s, int k) {
char alphaBet[] = "abcdefghijklmnopqrstuvwxyz";
int len = strlen(s);
if (len == 1 && s[0] < alphaBet[k-1]) {
s[0]++;
return s;
}
char* result = (char*)calloc(len + 1, sizeof(char));
strcpy(result, s);
为结果字符串分配内存，并将其初始化为输入字符串 s。同时处理字符串长度为1的特殊情况。
- 主循环
while (1) {
for (int i = len - 1; i >= 0; i--) {
if (result[i] < alphaBet[k - 1]) {
result[i]++;
for (int j = i + 1; j < len; j++) {
result[j] = alphaBet[0];
}
if (isBeauty(result, len)) {
return result;
}
break;
} else {
result[i] = alphaBet[0];
}
}
从字符串的末尾开始，逐个字符尝试将其增加，确保不包含回文子字符串。
- 检查所有字符是否达到最大值
bool allMax = true;
for (int i = 0; i < len; i++) {
if (result[i] != alphaBet[k - 1]) {
allMax = false;
break;
}
}
if (allMax) {
break;
}
}
free(result);
return strdup("");
检查是否所有字符都已经达到了最大值，如果是，则返回空字符串。
复杂度分析
- 时间复杂度：O(n*k)，因为每次字符的变化都需要检查整个字符串是否为美丽字符串。
- 空间复杂度：O(n)，因为需要额外的空间来存储结果字符串。
结果
官方题解
看不懂
char* generate(char* s, int idx, int offset) {
char* res = (char*)malloc(sizeof(char) * (strlen(s) + 1));
strcpy(res, s);
res[idx] += offset;
int len = strlen(s);
for (int i = idx + 1; i < len; ++i) {
char blockedCharacters[3] = {'\0'};
for (int j = 1; j < 3; ++j) {
if (i - j >= 0) {
blockedCharacters[j - 1] = res[i - j];
}
}
for (char c = 'a'; c <= 'c'; ++c) {
int isBlocked = 0;
for (int x = 0; x < 3; ++x) {
if (blockedCharacters[x] == c) {
isBlocked = 1;
break;
}
}
if (!isBlocked) {
res[i] = c;
break;
}
}
}
return res;
}
char * smallestBeautifulString(char * s, int k){
int length = strlen(s);
char* result = (char*)malloc(sizeof(char) * (length + 1));
strcpy(result, "");
for (int i = length - 1; i >= 0; --i) {
char blockedCharacters[3] = {'\0'};
for (int j = 1; j < 3; ++j) {
if (i - j >= 0) {
blockedCharacters[j - 1] = s[i - j];
}
}
for (int j = 1; j < 4; ++j) {
if (s[i] - 'a' + j + 1 <= k) {
int isBlocked = 0;
for (int x = 0; x < 3; ++x) {
if (blockedCharacters[x] == s[i] + j) {
isBlocked = 1;
break;
}
}
if (!isBlocked) {
sprintf(result, "%s", generate(s, i, j));
return result;
}
}
}
}
return result;
}
作者：力扣官方题解
链接：https://leetcode.cn/problems/lexicographically-smallest-beautiful-string/solutions/2814311/zi-dian-xu-zui-xiao-de-mei-li-zi-fu-chua-dr81/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。