পাইথনে স্ট্যাম্প ব্যবহার করে টার্গেট স্ট্রিং ফর্ম করার প্রোগ্রাম

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

উদাহরণস্বরূপ, প্রাথমিক সিকোয়েন্স "?????", স্ট্যাম্প "abc", তবে প্রথম টার্নে আমরা "abc??", "?abc?", "??abc" বানাতে পারি। যদি সিকোয়েন্সটি স্ট্যাম্প করা সম্ভব হয়, তবে প্রতিটি টার্নে বামপাশের লেটার স্ট্যাম্প হওয়ার ইন্ডেক্স ধারণকারী একটি অ্যারে রিটার্ন করুন। যদি সম্ভব না হয়, তবে খালি অ্যারে রিটার্ন করুন। তাই যখন সিকোয়েন্স "ababc" এবং স্ট্যাম্প "abc", তবে উত্তর হতে পারে [0, 2], কারণ "?????" -> "abc??" -> "ababc"।

উদাহরণস্বরূপ, ইনপুট s = "abcd", t = "abcdbcd" হলে আউটপুট হবে [3,0]।

সমাধানের ধাপসমূহ

• যদি len(s) == 1 হয়, তবে:

  • যদি t-এর সব ক্যারেক্টার s[0] সমান হয়, তবে 0 থেকে len(t) পর্যন্ত লিস্ট রিটার্ন করুন, অন্যথায় খালি লিস্ট

• ans := একটি নতুন লিস্ট

• t != "?" * len(t) থাকাকালীন লুপ চালান:

  • tmp := t

  • i = 0 থেকে len(s) পর্যন্ত লুপ চালান:

    • j = len(s) থেকে i+1 পর্যন্ত উল্টো লুপ চালান:

      • search := "?" * i + s[i:j] + "?" * (len(s)-j)

      • search t-এ থাকাকালীন লুপ চালান:

        • t.find(search)-কে ans-এর শেষে যোগ করুন

        • t := t.replace(search, "?"*len(s), 1)

      • যদি t == "?" * len(t) হয়, তবে লুপ থেকে বেরিয়ে আসুন

    • যদি t == "?" * len(t) হয়, তবে লুপ থেকে বেরিয়ে আসুন

  • যদি tmp == t হয়, তবে লুপ থেকে বেরিয়ে আসুন

• ans[::-1] রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালোভাবে বুঝার জন্য:

def solve(s, t):
    if len(s) == 1:
        return [i for i in range(len(t))] if all(ch == s[0] for ch 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]