Medium

题目描述

给你一个由小写英文字母组成的长度为 n 的字符串 s。

你必须执行恰好一次操作，选择任意整数 k，满足 1 <= k <= n，并且执行以下操作之一：

  • 翻转字符串 s 的前 k 个字符，或
  • 翻转字符串 s 的后 k 个字符。

返回执行恰好一次此类操作后可以获得的字典序最小的字符串。

示例 1：

输入：s = "dcab"
输出："acdb"
解释：
选择 k = 3，翻转前 3 个字符。
将 "dca" 翻转为 "acd"，得到字符串 s = "acdb"，这是可以达到的字典序最小的字符串。

示例 2：

输入：s = "abba"
输出："aabb"
解释：
选择 k = 3，翻转后 3 个字符。
将 "bba" 翻转为 "abb"，所以结果字符串是 "aabb"，这是可以达到的字典序最小的字符串。

示例 3：

输入：s = "zxy"
输出："xzy"
解释：
选择 k = 2，翻转前 2 个字符。
将 "zx" 翻转为 "xz"，所以结果字符串是 "xzy"，这是可以达到的字典序最小的字符串。

提示：

  • 1 <= n == s.length <= 1000
  • s 由小写英文字母组成

解题思路

思路分析

这道题要求我们通过一次翻转操作（翻转前k个或后k个字符）得到字典序最小的字符串。

暴力枚举法

由于字符串长度最大只有1000，我们可以采用暴力枚举的方法：

  1. 枚举所有可能的k值：从1到n，对每个k值分别尝试翻转前k个字符和翻转后k个字符
  2. 比较所有结果：将所有可能的结果字符串进行比较，找出字典序最小的那个

具体步骤：

  • 初始化结果为原字符串
  • 对于每个k从1到n：
    • 计算翻转前k个字符后的字符串
    • 计算翻转后k个字符后的字符串
    • 与当前最小结果比较，更新最小值
  • 返回最终的最小字符串

这种方法虽然时间复杂度较高，但由于数据规模较小且题目提示使用暴力法，是完全可行的解决方案。

代码实现

class Solution {
public:
    string lexSmallest(string s) {
        int n = s.length();
        string result = s;
        
        for (int k = 1; k <= n; k++) {
            // 翻转前k个字符
            string temp1 = s;
            reverse(temp1.begin(), temp1.begin() + k);
            if (temp1 < result) {
                result = temp1;
            }
            
            // 翻转后k个字符
            string temp2 = s;
            reverse(temp2.begin() + n - k, temp2.end());
            if (temp2 < result) {
                result = temp2;
            }
        }
        
        return result;
    }
};

class Solution:
    def lexSmallest(self, s: str) -> str:
        n = len(s)
        result = s
        
        for k in range(1, n + 1):
            # 翻转前k个字符
            temp1 = s[:k][::-1] + s[k:]
            if temp1 < result:
                result = temp1
            
            # 翻转后k个字符
            temp2 = s[:-k] + s[-k:][::-1]
            if temp2 < result:
                result = temp2
        
        return result

public class Solution {
    public string LexSmallest(string s) {
        int n = s.Length;
        string result = s;
        
        for (int k = 1; k <= n; k++) {
            // 翻转前k个字符
            char[] temp1 = s.ToCharArray();
            Array.Reverse(temp1, 0, k);
            string str1 = new string(temp1);
            if (string.Compare(str1, result) < 0) {
                result = str1;
            }
            
            // 翻转后k个字符
            char[] temp2 = s.ToCharArray();
            Array.Reverse(temp2, n - k, k);
            string str2 = new string(temp2);
            if (string.Compare(str2, result) < 0) {
                result = str2;
            }
        }
        
        return result;
    }
}

var lexSmallest = function(s) {
    const n = s.length;
    let result = s;
    
    for (let k = 1; k <= n; k++) {
        // 翻转前k个字符
        const temp1 = s.slice(0, k).split('').reverse().join('') + s.slice(k);
        if (temp1 < result) {
            result = temp1;
        }
        
        // 翻转后k个字符
        const temp2 = s.slice(0, n - k) + s.slice(n - k).split('').reverse().join('');
        if (temp2 < result) {
            result = temp2;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
暴力枚举O(n²)O(n)

说明：

  • 时间复杂度：O(n²)，需要枚举n个k值，每次操作需要O(n)时间进行字符串翻转和比较
  • 空间复杂度：O(n)，需要额外空间存储临时字符串