ধরুন আমাদের কাছে ছোট হাতের অক্ষর সহ একটি স্ট্রিং s আছে। আমাদেরকে s-এর মধ্যে সব খুঁজে বের করতে হবে যেখানে s-তে অন্য একটি সাবস্ট্রিং থাকতে হবে একটি ভিন্ন স্থানে যা সেই নেওয়া সাবস্ট্রিংগুলির একটি অ্যানাগ্রাম। আমাদের অভিধানিক ক্রমে সাবস্ট্রিংগুলির একটি তালিকা খুঁজে বের করতে হবে৷
সুতরাং, যদি ইনপুটটি s ="abcba" এর মত হয়, তাহলে আউটপুট হবে ['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba' , 'bc', 'bcba', 'cb', 'cba'] তাদের প্রত্যেকটির জন্য আমরা স্ট্রিংটিতেই উপস্থিত বিভিন্ন অ্যানাগ্রাম খুঁজে পেতে পারি।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
res :=একটি নতুন তালিকা
-
L :=s
এর আকার -
1 থেকে L রেঞ্জের জন্য, করুন
-
smap :=একটি খালি অভিধান, এবং সমস্ত মান টাইপ তালিকা
-
j-এর জন্য 0 থেকে L - i, করুন
-
cs :=ইনডেক্স j থেকে j + i-1]
পর্যন্ত s এর সাবস্ট্রিং -
k :=সাজানো আকারে cs-এর আইটেম যোগ করার পর স্ট্রিং
-
smap[k]
এর শেষে cs ঢোকান
-
-
smap-এ প্রতিটি কী k এবং মান v এর জন্য, করুন
-
যদি v>=2 এর আকার হয়, তাহলে
-
res
-এ v-এর উপাদান সন্নিবেশ করান
-
-
-
-
সাজানোর পরে রিটার্ন করুন
উদাহরণ
আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি
from collections import defaultdict def solve(s): res = [] L = len(s) for i in range(1, L + 1): smap = defaultdict(list) for j in range(L - i + 1): cs = s[j : j + i] k = "".join(sorted(cs)) smap[k].append(cs) for k, v in smap.items(): if len(v) >= 2: res.extend(v) return sorted(res) s = "abcba" print(solve(s))
ইনপুট
"abcba"
আউটপুট
['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']
