पायथन में संचालन लागू करने के बाद लेक्सिकोग्राफिक रूप से सबसे छोटी स्ट्रिंग खोजने का कार्यक्रम

मान लीजिए कि हमारे पास केवल संख्यात्मक अंकों के साथ एक स्ट्रिंग है और दो मान ए और बी भी हैं। हम निम्नलिखित दो संक्रियाओं में से किसी एक को कितनी भी बार और किसी भी क्रम में s -

. पर लागू कर सकते हैं

s(0-अनुक्रमित) की सभी विषम स्थिति वाली वस्तुओं में 'a' जोड़ें। यदि अंक 9 है, तो उसमें कुछ जोड़ने पर साइकिल वापस 0 पर आ जाएगी।
's' को b पोजीशन से दायीं ओर घुमाएं।

इसलिए हमें लेक्सिकोग्राफ़िक रूप से सबसे छोटी स्ट्रिंग ढूंढनी होगी जिसे हम उपरोक्त ऑपरेशनों को s पर कितनी भी बार लागू करके प्राप्त कर सकते हैं।

इसलिए, यदि इनपुट s ="5323" a =9 b =2 जैसा है, तो आउटपुट 2050 होगा क्योंकि यदि हम अनुसरण करते हैं

घुमाएँ:"5323"
जोड़ें:"5222"
जोड़ें:"5121"
घुमाएँ:"2151"
जोड़ें:"2050"

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

देखा:=एक नया सेट
deq :=एक तत्व 'एस' के साथ एक नई कतार
जबकि deq खाली नहीं है, करें
- curr :=deq के पहले हटाए गए तत्व
- देखे गए सेट में करंट डालें
- विज्ञापन :=curr पर दिए गए ऐड ऑपरेशन को निष्पादित करें
- यदि विज्ञापन दिखाई नहीं दे रहा है, तो
  - डीक्यू के अंत में विज्ञापन डालें
  - देखे गए सेट में विज्ञापन डालें
- ro :=कर्व पर रोटेट ऑपरेशन करें
- यदि 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