পাইথনে স্টাকি কীবোর্ড কী চেক করা (টাইপড স্ট্রিং টার্গেট থেকে বড় কিনা)

দুটি স্ট্রিং s (টাইপড) এবং t (টার্গেট) দেওয়া আছে। কীবোর্ডের কী স্টাক থাকতে পারে, তাই একটি ক্যারেক্টার ১ বা অধিকবার টাইপ হতে পারে। s কি t লিখতে গিয়ে তৈরি হতে পারে? চেক করুন।

ইনপুট উদাহরণ

s = "appppleee"
t = "apple"

আউটপুট: True

অ্যালগরিদম

1. দুই পয়েন্টার i (s-এর জন্য), j (t-এর জন্য)।
2. যদি s[i] == t[j]: উভয় বাড়ান, t_last = t[j]।
3. যদি s[i] == t_last: শুধু i++ (রিপিটেড কী)।
4. অন্যথায়: False।
5. শেষে s-এর বাকি ক্যারেক্টার সব t_last হলে True।

পাইথন কোড

def solve(s, t):
    i = j = 0
    s_len = len(s)
    t_len = len(t)
    t_last = ""
    while j < t_len:
        if i == s_len:
            return False
        if s[i] == t[j]:
            t_last = t[j]
            i += 1
            j += 1
        elif s[i] == t_last:
            i += 1
        else:
            return False
    if i < s_len:
        return all(char == t_last for char in s[i:])
    else:
        return True

# টেস্ট
print(solve("appppleee", "apple"))  # True

ব্যাখ্যা

গ্রিডি ম্যাচিং: টার্গেটের ক্যারেক্টার ম্যাচ করাতে হলে, এক্সট্রা ক্যারেক্টার শুধু শেষ ম্যাচ করা ক্যারেক্টারের রিপিট হতে পারে। সময় O(n+m)।