পাইথনে বর্গাকার অ্যারের সংখ্যা খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমরা ছোট হাতের অক্ষরের একটি টার্গেট স্ট্রিং তৈরি করতে চাই। প্রথমে, আমরা n '?' হিসাবে ক্রম আছে চিহ্ন (n হল টার্গেট স্ট্রিং এর দৈর্ঘ্য)। আমরা ছোট হাতের অক্ষর একটি স্ট্যাম্প আছে. প্রতিটি মোড়ে, আমরা সিকোয়েন্সের উপর স্ট্যাম্প স্থাপন করতে পারি এবং সেই স্ট্যাম্পের সংশ্লিষ্ট অক্ষর দিয়ে প্রতিস্থাপন করতে পারি। আপনি 10 * n টার্ন পর্যন্ত করতে পারেন।

একটি উদাহরণ হিসাবে বিবেচনা করুন প্রাথমিক ক্রম হল "??????", এবং স্ট্যাম্প হল "abc", তাহলে আমরা প্রথমে "abc??", "? abc?", "?? abc" এর মত স্ট্রিং তৈরি করতে পারি। পালা যদি ক্রমটি স্ট্যাম্প করা সম্ভব হয়, তাহলে প্রতিটি মোড়ে স্ট্যাম্প করা বাম-সবচেয়ে অক্ষর সহ সূচকের একটি অ্যারে ফেরত দিন। যদি তা সম্ভব না হয় তাহলে একটি খালি অ্যারে ফেরত দিন। সুতরাং যখন ক্রমটি "ababc" হয়, এবং স্ট্যাম্প হয় "abc", তখন উত্তরটি [0, 2] এর মতো হতে পারে, কারণ আমরা "????" এর মতো গঠন করতে পারি। -> "abc??" -> "ababc"।

সুতরাং, যদি ইনপুট s ="abcd" t ="abcdbcd" এর মত হয়, তাহলে আউটপুট হবে [3,0]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি s এর আকার 1 এর সমান হয়, তাহলে

  • 0 থেকে t একটি তালিকা ফেরত দিন যখন t-এর সমস্ত অক্ষর একই থাকে এবং তারা s[0] হয়, অন্যথায় একটি নতুন ফাঁকা তালিকা

• উত্তর :=একটি নতুন তালিকা

• যদিও t "?" এর টি সংখ্যার আকারের সমান নয়। চিহ্ন, কর

  • tmp :=t

  • 0 থেকে s আকারের রেঞ্জের জন্য, করুন

    • j-এর জন্য s এর আকার i+1:

      -এ নেমে আসে

      • অনুসন্ধান :=i সংখ্যা "?" s [সূচী i থেকে j-1 পর্যন্ত] কনক্যাটেনেট সাবস্ট্রিং (s - j-এর আকার) "?"

      • অনুসন্ধান করার সময়, করুন

        • সন্নিবেশ করুন যেখানে অনুসন্ধান উত্তরের শেষে t তে উপস্থিত রয়েছে

        • t :="?" এর s সংখ্যার আকার দিয়ে অনুসন্ধান প্রতিস্থাপন করুন শুধুমাত্র একবার

      • যদি t "?" এর t সংখ্যার আকারের সমান হয়, তাহলে

        • লুপ থেকে বেরিয়ে আসুন

      • যদি t "?" এর t সংখ্যার আকারের সমান হয়, তাহলে

        • লুপ থেকে বেরিয়ে আসুন

    • tmp যদি t এর মত হয়, তাহলে

      • লুপ থেকে বেরিয়ে আসুন

• উত্তরের বিপরীত ফেরত দিন।

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

def solve(s, t):
   if len(s) == 1:
      return [i for i in range(len(t))] if all(t==s[0] for t in t)else []

   ans = []
   while t != "?" * len(t):
      tmp = t
      for i in range(len(s)):
         for j in reversed(range(i+1, len(s)+1)):
            search = "?" * i + s[i:j] + "?" * (len(s)-j)
            while t.find(search) != -1:
               ans.append(t.find(search))
               t = t.replace(search, "?"*len(s), 1)
            if t == "?" * len(t): break
         if t == "?" * len(t): break
      if tmp == t: return []
   return ans[::-1]

s = "abcd"
t = "abcdbcd"
print(solve(s, t))

ইনপুট

"abcd", "abcdbcd"

আউটপুট

[3,0]