How do rotation and addition operations work in this problem?

Rotation shifts the digits of the string, while addition modifies a specific digit by adding a number between 0 and 9. Both operations can be applied any number of times to optimize the string.

What is the role of depth-first search in this problem?

Depth-first search is used to explore all possible states generated by the operations. It systematically checks different operation sequences and finds the lexicographically smallest string.

What is the time complexity of this problem?

The time complexity depends on the final approach but can grow exponentially due to the large number of possible operation sequences. Optimization through memoization can help reduce this.

How can I optimize my solution for larger inputs?

Optimizing the solution can be done by using memoization or pruning to avoid recalculating the same string states. This can greatly reduce time complexity in larger inputs.

What is the primary pattern to solve this problem?

The primary pattern is string manipulation combined with depth-first search (DFS), which allows us to explore all possible operations and find the lexicographically smallest result.

#1625

Medium

auto_awesome图·搜索

LeetCode 题解工作台

执行操作后字典序最小的字符串

给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。你可以在 s 上按任意顺序多次执行下面两个操作之一：累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。当数字超过 9 时，从 0 重新循环计算。例如， s = "…

字符串深度优先搜索广度优先搜索枚举

题目描述

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

你可以在 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"
解释：执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"
无法获得字典序小于 "24" 的字符串。

示例 3：

输入：s = "0011", a = 4, b = 2
输出："0011"
解释：无法获得字典序小于 "0011" 的字符串。

提示：

2 <= s.length <= 100
s.length 是偶数
s 仅由数字 0 到 9 组成
1 <= a <= 9
1 <= b <= s.length - 1

lightbulb

解题思路

方法一：BFS

本题数据规模较小，我们可以使用 BFS 暴力搜索所有可能的状态，然后取字典序最小的状态即可。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findLexSmallestString(self, s: str, a: int, b: int) -> str:
        q = deque([s])
        vis = {s}
        ans = s
        while q:
            s = q.popleft()
            if ans > s:
                ans = s
            t1 = ''.join(
                [str((int(c) + a) % 10) if i & 1 else c for i, c in enumerate(s)]
            )
            t2 = s[-b:] + s[:-b]
            for t in (t1, t2):
                if t not in vis:
                    vis.add(t)
                    q.append(t)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate's understanding of depth-first search (DFS) and breadth-first search (BFS) will be crucial to solving the problem.
question_mark
The candidate should highlight ways to optimize the solution using memoization or pruning techniques to handle large input sizes.
question_mark
Look for the candidate's ability to balance both rotation and addition operations effectively within the string manipulation strategy.

warning

常见陷阱

外企场景

error
Forgetting to handle the pruning of unpromising paths in DFS can lead to unnecessary computations.
error
Incorrectly applying rotation and addition operations could result in non-optimal solutions.
error
Overcomplicating the algorithm by missing opportunities for memoization to optimize repeated states.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the number of operations allowed to test optimization techniques.
arrow_right_alt
Consider a variation where the string length is odd, requiring different traversal strategies.
arrow_right_alt
Modify the problem to handle larger digit sets or constraints to test scalability.

help

常见问题

外企场景

继续练习

#1202 交换字符串中的元素 #839 相似字符串组 #721 账户合并