मान लीजिए कि हमारे पास दो तार s और t हैं। ये दो तार K-समान हैं यदि हम दो अक्षरों की स्थिति को s ठीक K बार में स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग t हो। तो, हमारे पास दो विपर्यय s और t हैं, हमें सबसे छोटा K ज्ञात करना है जिसके लिए s और t K-समान हैं।
इसलिए, यदि इनपुट s ="abc" t ="bac" जैसा है, तो आउटपुट 1 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक फ़ंक्शन पड़ोसियों() को परिभाषित करें। इसमें नया_डेटा लगेगा
-
new_data में प्रत्येक अनुक्रमणिका i और मान c के लिए, करें
-
यदि c, t[i] के समान नहीं है, तो
-
लूप से बाहर आएं
-
-
-
j के लिए i+1 से लेकर new_data - 1 के आकार की श्रेणी में, करें
-
यदि आप [j] t[i] के समान हैं, तो
-
एक्सचेंज new_data[i] new_data[j]
-
new_data से सभी तत्वों को जोड़कर एक स्ट्रिंग उत्पन्न करें और अगली कॉल से वापस लौटें, इस क्षेत्र से फिर से शुरू करें
-
एक्सचेंज new_data[i] new_data[j]
-
-
-
मुख्य विधि से, निम्न कार्य करें:
-
q :=एक कतार बनाएं उत्तर जोड़ी डालें (ओं, 0)
-
देखा :=एस से एक नया सेट
-
जबकि q खाली नहीं है, करें
-
(u, swap_cnt) :=q का पहला आइटम और इसे q से हटा दें
-
यदि आप t के समान हैं, तो
-
वापसी swap_cnt
-
-
पड़ोसियों में प्रत्येक वी के लिए (यू सूची के रूप में), करो
-
अगर v दिखाई नहीं दे रहा है, तो
-
v को देखा के रूप में चिह्नित करें
-
q के अंत में (v, swap_cnt+1) डालें
-
-
-
-
वापसी 0
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
from collections import deque
def solve(s, t):
def swap(data, i, j):
data[i], data[j] = data[j], data[i]
def neighbors(new_data):
for i, c in enumerate(new_data):
if c != t[i]: break
for j in range(i+1, len(new_data)):
if u[j] == t[i]:
swap(new_data, i, j)
yield "".join(new_data)
swap(new_data, i, j)
q = deque([(s, 0)])
seen = set(s)
while q:
u, swap_cnt = q.popleft()
if u == t:
return swap_cnt
for v in neighbors(list(u)):
if v not in seen:
seen.add(v)
q.append((v, swap_cnt+1))
return 0
s = "abc"
t = "bac"
print(solve(s, t)) इनपुट
"abc, bac"
आउटपुट
1