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

Z时代
2024-01-10
分类：综合

假设我们有一个只有数字的字符串 s 并且还有两个值 a 和 b。我们可以在 s 上以任意顺序应用以下两种操作中的任意一种 -

将 'a' 添加到 s（0 索引）的所有奇数定位项。如果数字是 9，那么通过添加一些东西将循环回 0。
将 's' 向右旋转 b 个位置。

因此，我们必须通过对 s 进行任意次数的上述操作，才能找到按字典顺序排列的最小字符串。

因此，如果输入类似于 s = "5323" a = 9 b = 2，那么输出将是 2050，因为如果我们遵循

旋转：“5323”
添加：“5222”
添加：“5121”
旋转：“2151”
添加：“2050”

示例

让我们看看以下实现以获得更好的理解 -

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))