Medium

题目描述

给你一个偶数长度的字符串 s，由数字 0 到 9 组成，以及两个整数 a 和 b。

你可以在 s 上按任意顺序执行以下两种操作任意次数：

  • 将 a 加到 s 的所有奇数下标上（下标从 0 开始）。数字超过 9 后会回到 0。例如，如果 s = "3456" 且 a = 5，则 s 变为 "3951"。
  • 将 s 向右旋转 b 个位置。例如，如果 s = "3456" 且 b = 1，则 s 变为 "6345"。

通过对 s 执行上述操作任意次数，返回你能得到的字典序最小的字符串。

字符串 a 在字典序上小于字符串 b（长度相同）是指在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符在字母表中的出现位置比字符串 b 中的对应字符更靠前。例如，"0158" 在字典序上小于 "0190"，因为它们第一次不同是在第三个位置，而 '5' 在 '9' 之前。

示例 1：

输入：s = "5525", a = 9, b = 2
输出："2050"
解释：我们可以执行以下操作：
开始：  "5525"
旋转： "2555"
加：    "2454"
加：    "2353"
旋转： "5323"
加：    "5222"
加：    "5121"
旋转： "2151"
加：    "2050"
无法得到字典序比 "2050" 更小的字符串。

示例 2：

输入：s = "74", a = 5, b = 1
输出："24"

示例 3：

输入：s = "0011", a = 4, b = 2
输出："0011"

提示：

  • 2 <= s.length <= 100
  • s.length 是偶数
  • s 只包含数字 0 到 9
  • 1 <= a <= 9
  • 1 <= b <= s.length - 1

解题思路

这道题需要通过两种操作找到字典序最小的字符串。关键观察：

  1. 操作特性分析：

    • 操作1只能修改奇数位置的数字，且每次加固定值a（模10）
    • 操作2是循环右移，可以改变哪些位置是奇数位置

  2. 状态空间有限性：

    • 对于每个奇数位置，最多有10种不同的数字（0-9）
    • 旋转操作最多有n种不同状态（n为字符串长度）
    • 总状态数有限，可以用BFS/DFS遍历所有可能状态

  3. 解法思路：

    • 使用BFS遍历所有可能的状态
    • 对于每个状态，尝试两种操作：加a到奇数位置、右移b位
    • 用set记录访问过的状态避免重复
    • 维护遇到的字典序最小字符串

  4. 优化考虑：

    • 由于要找字典序最小，可以用BFS确保按层次遍历
    • 也可以用DFS + 全局最小值比较

推荐使用BFS解法，逻辑清晰且容易理解。

代码实现

class Solution {
public:
    string findLexSmallestString(string s, int a, int b) {
        unordered_set<string> visited;
        queue<string> q;
        q.push(s);
        visited.insert(s);
        string result = s;
        
        while (!q.empty()) {
            string current = q.front();
            q.pop();
            
            if (current < result) {
                result = current;
            }
            
            // 操作1：给奇数位置加a
            string add_a = current;
            for (int i = 1; i < add_a.length(); i += 2) {
                add_a[i] = '0' + (add_a[i] - '0' + a) % 10;
            }
            if (visited.find(add_a) == visited.end()) {
                visited.insert(add_a);
                q.push(add_a);
            }
            
            // 操作2：右移b位
            string rotate = current.substr(current.length() - b) + current.substr(0, current.length() - b);
            if (visited.find(rotate) == visited.end()) {
                visited.insert(rotate);
                q.push(rotate);
            }
        }
        
        return result;
    }
};

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        from collections import deque
        
        visited = set()
        queue = deque([s])
        visited.add(s)
        result = s
        
        while queue:
            current = queue.popleft()
            
            if current < result:
                result = current
            
            # 操作1：给奇数位置加a
            add_a = list(current)
            for i in range(1, len(add_a), 2):
                add_a[i] = str((int(add_a[i]) + a) % 10)
            add_a_str = ''.join(add_a)
            
            if add_a_str not in visited:
                visited.add(add_a_str)
                queue.append(add_a_str)
            
            # 操作2：右移b位
            rotate = current[-b:] + current[:-b]
            if rotate not in visited:
                visited.add(rotate)
                queue.append(rotate)
        
        return result

public class Solution {
    public string FindLexSmallestString(string s, int a, int b) {
        var visited = new HashSet<string>();
        var queue = new Queue<string>();
        queue.Enqueue(s);
        visited.Add(s);
        string result = s;
        
        while (queue.Count > 0) {
            string current = queue.Dequeue();
            
            if (string.Compare(current, result) < 0) {
                result = current;
            }
            
            // 操作1：给奇数位置加a
            char[] addA = current.ToCharArray();
            for (int i = 1; i < addA.Length; i += 2) {
                addA[i] = (char)('0' + (addA[i] - '0' + a) % 10);
            }
            string addAStr = new string(addA);
            
            if (!visited.Contains(addAStr)) {
                visited.Add(addAStr);
                queue.Enqueue(addAStr);
            }
            
            // 操作2：右移b位
            string rotate = current.Substring(current.Length - b) + current.Substring(0, current.Length - b);
            if (!visited.Contains(rotate)) {
                visited.Add(rotate);
                queue.Enqueue(rotate);
            }
        }
        
        return result;
    }
}

/**
 * @param {string} s
 * @param {number} a
 * @param {number} b
 * @return {string}
 */
var findLexSmallestString = function(s, a, b) {
    const visited = new Set();
    const queue = [s];
    let result = s;
    
    while (queue.length > 0) {
        const current = queue.shift();
        
        if (visited.has(current)) continue;
        visited.add(current);
        
        if (current < result) {
            result = current;
        }
        
        // Operation 1: Add a to all odd indices
        let op1 = '';
        for (let i = 0; i < current.length; i++) {
            if (i % 2 === 1) {
                op1 += ((parseInt(current[i]) + a) % 10).toString();
            } else {
                op1 += current[i];
            }
        }
        
        // Operation 2: Rotate right by b positions
        const op2 = current.slice(-b) + current.slice(0, -b);
        
        queue.push(op1, op2);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(10 × n × L) 其中 n 是字符串长度，L 是可能的状态总数。奇数位最多10种状态，旋转最多n种状态，所以总状态数约为 10×n
空间复杂度O(10 × n) 用于存储访问过的状态集合和BFS队列

相关题目