मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं। ये दो स्ट्रिंग्स K-समान हैं यदि हम s में दो अक्षरों की स्थितियों को ठीक K बार स्वैप कर सकते हैं ताकि परिणामी स्ट्रिंग t हो जाए। तो, हमारे पास दो एनाग्राम s और t हैं, हमें सबसे छोटा K ढूंढना है जिसके लिए s और t K-समान हैं।
उदाहरण के लिए, यदि इनपुट है s = "abc" t = "bac", तो आउटपुट 1 होगा।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्न चरणों का पालन करेंगे:
neighbors() फंक्शन परिभाषित करें। यह new_data लेगा
new_data में प्रत्येक इंडेक्स i और मान c के लिए
यदि c, t[i] के समान नहीं है, तो लूप से बाहर निकलें
j के लिए i+1 से new_data के आकार - 1 तक लूप चलाएं
यदि u[j], t[i] के समान है, तो
new_data[i] और new_data[j] को एक्सचेंज करें
new_data के सभी तत्वों को जोड़कर एक स्ट्रिंग जनरेट करें और लौटाएं, अगले कॉल से इस क्षेत्र से फिर से शुरू करें
new_data[i] और new_data[j] को वापस एक्सचेंज करें
मुख्य विधि से, निम्न करें:
q := एक क्यू बनाएं और युग्म (s, 0) डालें
seen := s से एक नया सेट
जब तक q खाली नहीं है
(u, swap_cnt) := q का पहला आइटम और इसे q से हटाएं
यदि u, t के समान है, तो swap_cnt लौटाएं
u को सूची के रूप में neighbors() के प्रत्येक v के लिए
यदि v, seen में नहीं है, तो
v को seen के रूप में मार्क करें
(v, swap_cnt+1) को q के अंत में डालें
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
