当前位置：首页 > article >正文

37构造回文字符串问题-青训营刷题

article 2025/2/8 14:31:23

问题描述

小C手中有一个由小写字母组成的字符串 s。她希望构造另一个字符串 t，并且这个字符串需要满足以下几个条件：

t 由小写字母组成，且长度与 s 相同。
t 是回文字符串，即从左到右与从右到左读取相同。
t 的字典序要小于 s，并且在所有符合条件的字符串中字典序尽可能大。

小C想知道是否能构造出这样的字符串 t，输出这样的t。如果无法构造满足条件的字符串，则输出 -1。

测试样例

样例1：

输入：s = "abc"
输出：'aba'

样例2：

输入：s = "cba"
输出：'cac'

样例3：

输入：s = "aaa"
输出：'-1'

代码如下

public class Main {
    public static String solution(String s) {
        int n = s.length();
        char[] t = s.toCharArray();  // 转换为字符数组，方便修改

        // 先构建一个回文字符串
        for (int i = 0; i < n / 2; ++i) {
            t[n - i - 1] = t[i];  // 保持回文性
        }

        // 如果初始回文字符串已经小于s，直接返回
        if (new String(t).compareTo(s) < 0) {
            return new String(t);
        }

        // 否则，从中间开始向前调整
        for (int i = (n - 1) / 2; i >= 0; --i) {
            if (t[i] > 'a') {  // 如果当前字符大于 'a'，可以减小
                t[i] = (char)(t[i] - 1);
                t[n - i - 1] = t[i];  // 保持回文性

                // 调整后面的位置为尽可能的小字符 'z'，确保字典序最小
                for (int j = i + 1; j < n - i - 1; ++j) {
                    t[j] = 'z';
                    t[n - j - 1] = t[j];
                }

                // 生成回文字符串并检查字典序
                String tStr = new String(t);
                if (tStr.compareTo(s) < 0) {
                    return tStr;
                } else {
                    // 如果调整后仍然不满足条件，继续尝试下一个字符
                    t[i] = s.charAt(i);
                    t[n - i - 1] = s.charAt(i);
                }
            }
        }

        return "-1";
    }

    public static void main(String[] args) {
        System.out.println(solution("abc").equals("aba"));  // 输出 true
        System.out.println(solution("cba").equals("cac"));  // 输出 true
        System.out.println(solution("aaa").equals("-1"));  // 输出 true
    }
}

代码解释

这段代码实现了一个算法，目标是找到一个字典序小于给定字符串 s 的最长回文字符串。如果找不到这样的字符串，则返回 -1。以下是对代码的详细解释：

1. 问题背景

给定一个字符串 s，需要找到一个字典序小于 s 的最长回文字符串。
字典序是指按照字符顺序比较字符串的大小，例如 "aba" 小于 "abc"。
回文字符串是指正读和反读都相同的字符串，例如 "aba"、"cac"。

2. 代码逻辑

输入和输出

输入：一个字符串 s。
输出：一个字典序小于 s 的最长回文字符串，或者 -1（如果不存在这样的字符串）。

主要步骤

构建初始回文字符串
- 将字符串 s 转换为字符数组 t，方便修改。
- 通过将后半部分的字符设置为前半部分的对应字符，构建一个回文字符串。
java复制
```
for (int i = 0; i < n / 2; ++i) {
    t[n - i - 1] = t[i];  // 保持回文性
}
```
- 例如，对于输入 "abc"，初始回文字符串为 "aca"。
检查初始回文字符串是否满足条件
- 如果初始回文字符串的字典序小于 s，直接返回该回文字符串。
java复制
```
if (new String(t).compareTo(s) < 0) {
    return new String(t);
}
```
- 例如，对于输入 "abc"，初始回文字符串 "aca" 小于 "abc"，因此直接返回 "aca"。
从中间向前调整字符
- 如果初始回文字符串不满足条件，则从中间字符开始向前调整。
- 对于每个字符，尝试将其减小（例如从 'b' 减到 'a'），并更新回文字符串。
- 同时，将调整后的字符对称位置也更新为相同的字符，以保持回文性。
java复制
```
for (int i = (n - 1) / 2; i >= 0; --i) {
    if (t[i] > 'a') {  // 如果当前字符大于 'a'，可以减小
        t[i] = (char)(t[i] - 1);
        t[n - i - 1] = t[i];  // 保持回文性
```
- 例如，对于输入 "cba"，初始回文字符串为 "cac"，不满足条件。调整中间字符 'c' 为 'b'，得到 "bab"。
调整后续字符为最小字符
- 在调整当前字符后，将后续字符（即中间字符之后的部分）设置为 'z'，以确保生成的回文字符串字典序最小。
java复制
```
for (int j = i + 1; j < n - i - 1; ++j) {
    t[j] = 'z';
    t[n - j - 1] = t[j];
}
```
- 例如，对于输入 "cba"，调整中间字符后，后续字符设置为 'z'，得到 "bazbz"。
检查调整后的回文字符串是否满足条件
- 如果调整后的回文字符串字典序小于 s，则返回该字符串。
java复制
```
String tStr = new String(t);
if (tStr.compareTo(s) < 0) {
    return tStr;
}
```
- 如果调整后的回文字符串仍然不满足条件，则恢复当前字符为原始值，继续尝试下一个字符。
java复制
```
t[i] = s.charAt(i);
t[n - i - 1] = s.charAt(i);
```
返回结果
- 如果所有字符都无法调整出满足条件的回文字符串，则返回 -1。
java复制
```
return "-1";
```