Pythonで操作を適用した後、辞書式に最小の文字列を見つけるプログラム

数字のみの文字列sがあり、2つの値aとbもあるとします。次の2つの操作のいずれかを、s −

• s（0-indexed）のすべての奇数位置のアイテムに「a」を追加します。数字が9の場合、何かを追加すると0に戻ります。

• 's'をbの位置だけ右に回転させます。

したがって、上記の操作をsに何度でも適用することで、辞書式順序で最小の文字列を見つける必要があります。

したがって、入力がs ="5323" a =9 b =2のような場合、出力は2050になります。

• 回転：「5323」
• 追加：「5222」
• 追加： "5121"
• 回転：「2151」
• 追加：「2050」

これを解決するには、次の手順に従います-

• 見た：=新しいセット
• deq：=1つの要素's'を持つ新しいキュー
• deqが空でない間は、
  • curr：=deqの最初に削除された要素
  • 見たセットにcurrを挿入
  • ad：=currで特定の追加操作を実行する
  • 広告が表示されない場合は、
    • deqの最後に広告を挿入
    • 表示されたセットに広告を挿入
  • ro：=currで回転操作を実行する
  • roが表示されていない場合は、
    • deqの最後にroを挿入
    • 見たセットにroを挿入
• 見たものの最小値を返す

例

理解を深めるために、次の実装を見てみましょう-

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

入力

"5323", 9, 2

出力

2050