泰州东方医院,网站分析与优化,派点网站建设,自己做免流网站题目
如果一个字符串满足以下条件#xff0c;则称其为 美丽字符串 #xff1a;
它由英语小写字母表的前 k 个字母组成。它不包含任何长度为 2 或更长的回文子字符串。
给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
请你找出并返回一个长度为 n 的美丽字符串#…题目
如果一个字符串满足以下条件则称其为 美丽字符串
它由英语小写字母表的前 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 的字符串。
思路
前提如果字符串不包含任何长度为 2 和 3 的回文子字符串则该字符串根本不包含任何回文子字符串。
题目简单来说就是在有限的字母范内给你一个没有回文子字符串的字符串返回比这个字符串大的最小字符串注意要在范围内否则返回空字符串。
解题方法
由于原字符串已经是美丽字符串所以我们只需要将最后一位加1进行判断首先看有没有超出字母范围如果超出赋最小的值a进位判断是否能进位不能返归空字符串。再判断是否构成回文字符串i0str[i]str[i-1]||i1str[i]str[i-2]是的话数值加一否则在in里判断后面是否构成回文字符串。构成就加1不构成i,每一次都会判断有没有超出字母范围如果超出赋最小的值a进位。
代码
class Solution {public String smallestBeautifulString(String s, int k) {int ns.length();kka;char[] strs.toCharArray();int in-1;str[i];while(in){if(str[i]k){if(i0){return ;}str[i]a;str[--i];}else if(i0str[i]str[i-1]||i1str[i]str[i-2]){str[i];}else{i;}}return new String(str);}
}
