মনে করুন আমাদের কাছে s এবং t নামে দুটি স্ট্রিং আছে। এই দুটি স্ট্রিং K-similar হবে যদি আমরা s-এ দুটি লেটারের পজিশন সোয়াপ করে ঠিক K বার করলে ফলাফল t হয়। সুতরাং, আমাদের দুটি एনাগ্রাম s এবং t দেওয়া আছে, আমাদের সবচেয়ে ছোট K বের করতে হবে যাতে s এবং t K-similar হয়।
সুতরাং, যদি ইনপুট হয় 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(u as list)-এ প্রতিটি v-এর জন্য, করুন
যদি v seen-এ না থাকে, তবে
v কে seen হিসেবে মার্ক করুন
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
