在 Python 中应用操作后查找字典顺序最小字符串的程序

pythonserver side programmingprogramming更新于 2025/11/30 2:20:17

假设我们有一个字符串 s，其中只有数字，还有两个值 a 和 b。我们可以对 s − 应用以下两个操作中的任意一个，次数和顺序均可。

将"a"添加到 s(从 0 开始索引)的所有奇数位置项。如果数字为 9，则通过添加某个值将循环回 0。
将"s"向右旋转 b 个位置。

因此，我们必须通过对 s 应用上述操作任意次，找到我们可以获得的字典顺序最小的字符串。

因此，如果输入为 s = "5323" a = 9 b = 2，则输出将为 2050，因为如果我们遵循

旋转:"5323"
添加:"5222"
添加:"5121"
旋转:"2151"
添加:"2050"

为了解决这个问题，我们将遵循以下步骤 −

seen := 一个新集合
deq := 一个包含一个元素"s"的新队列
当 deq 不为空时，执行
- curr := 第一个被删除的元素deq
- 将 curr 插入到 seen 集合中
- ad := 对 curr 执行给定的添加操作
- 如果 ad 不在 seen 中，则
  - 在 deq 末尾插入 ad
  - 将 ad 插入到 seen 集合中
- ro := 对 curr 执行旋转操作
- 如果 ro 不在 seen 中，则
  - 在 deq 末尾插入 ro
  - 将 ro 插入 seen 集合中
返回 seen 的最小值

示例

让我们看看下面的实现以便更好地理解 −


from collections import deque
def add_(s,a):
   res = ''
   for idx, i in enumerate(s):
      if idx % 2 == 1:
         num = (int(i) + a) % 10
         res += str(num)
      else:
         res += i

   return res

def rotate_(s, b):
   idx = len(s)-b
   res = s[idx:] + s[0:idx]
   return res

def solve(s, a, b):
   seen = set()
   deq = deque([s])

   while deq:
      curr = deq.popleft()
      seen.add(curr)

      ad = add_(curr, a)
      if ad not in seen:
         deq.append(ad)
         seen.add(ad)

      ro = rotate_(curr, b)
      if ro not in seen:
         deq.append(ro)
         seen.add(ro)

   return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))