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

假设我们有一个仅由数字组成的字符串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’
while deq不为空，执行以下操作
- curr：=删除deq的第一个元素
- 将curr插入seen集合
- ad：=对curr执行给定的添加操作
- 如果ad不在seen中，则
  - 将ad插入到deq的末尾
  - 将ad插入seen集合中
- ro：=对curr执行旋转操作
- 如果ro不在seen中，则
  - 将ro插入到deq的末尾
  - 将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))