Python में ऑपरेशन लागू करने के बाद लेक्सिकोग्राफिकली सबसे छोटी स्ट्रिंग खोजने का प्रोग्राम

मान लीजिए हमारे पास केवल संख्यात्मक अंकों वाली एक स्ट्रिंग s है और दो मान a और b भी हैं। हम s पर निम्नलिखित दो ऑपरेशन्स में से किसी एक को किसी भी क्रम में कितनी भी बार लागू कर सकते हैं:

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

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

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

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

समाधान के चरण

seen := set()
deq := deque([s]) (एक एलिमेंट s वाली क्यू)
while deq:
- curr := deq.popleft()
- seen.add(curr)
- ad := curr पर दिया गया जोड़ ऑपरेशन करें
- यदि ad not in seen:
  - deq.append(ad)
  - seen.add(ad)
- ro := curr पर घुमाव ऑपरेशन करें
- यदि ro not in seen:
  - deq.append(ro)
  - seen.add(ro)
min(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))

इनपुट

"5323", 9, 2