ধরুন আমাদের দুটি স্ট্রিং s এবং t আছে। এই দুটি স্ট্রিং K- অনুরূপ যদি আমরা s ঠিক K সময়ে দুটি অক্ষরের অবস্থান অদলবদল করতে পারি যাতে ফলস্বরূপ স্ট্রিং টি হয়। সুতরাং, আমাদের দুটি অ্যানাগ্রাম s এবং t আছে, আমাদের সবচেয়ে ছোট K খুঁজে বের করতে হবে যার জন্য s এবং t K- অনুরূপ।
সুতরাং, যদি ইনপুট s ="abc" t ="bac" এর মত হয়, তাহলে আউটপুট হবে 1।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন প্রতিবেশী() সংজ্ঞায়িত করুন। এটি নতুন_ডেটা গ্রহণ করবে
-
new_data-এ প্রতিটি সূচক i এবং মানের c-এর জন্য, করুন
-
যদি c টি[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)
-
দেখা হয়েছে :=s
থেকে একটি নতুন সেট -
q খালি না থাকার সময়, করুন
-
(u, swap_cnt) :=q এর প্রথম আইটেম এবং q থেকে মুছুন
-
আপনি যদি t এর মতই হন, তাহলে
-
swap_cnt
ফেরত দিন
-
-
প্রতিবেশীদের মধ্যে প্রতিটি v এর জন্য (তালিকা হিসাবে u), করুন
-
যদি 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
