পাইথনে শব্দের তালিকা থেকে সাবসিকোয়েন্স সংখ্যা গণনা করার প্রোগ্রাম

ধরুন একটি শব্দের তালিকা এবং একটি স্ট্রিং s আছে। আমাদের তালিকার কতগুলো শব্দ s-এর সাবসিকোয়েন্স তা বের করতে হবে।

উদাহরণ: words = ["xz", "xw", "y"], s = "xyz" → আউটপুট ২ ("xz" এবং "y" সাবসিকোয়েন্স)।

সমাধানের ধাপগুলো:

ans = 0, d খালি ম্যাপ।
প্রতিটি শব্দের প্রথম অক্ষর অনুযায়ী d-এ রাখুন।
s-এর প্রতিটি অক্ষর c için: l = d[c], d[c] = []।
l-এর প্রতিটি শব্দের জন্য: দৈর্ঘ্য ১ হলে ans++, অন্যথায় বাকি অংশ d[word[1]]-এ যোগ করুন।
শেষে ans রিটার্ন করুন।

উদাহরণ

from collections import defaultdict
class Solution:
    def solve(self, words, s):
        ans = 0
        d = defaultdict(list)
        for word in words:
            d[word[0]].append(word)
        for c in s:
            l = d[c]
            d[c] = []
            for word in l:
                if len(word) == 1:
                    ans += 1
                else:
                    d[word[1]].append(word[1:])
        return ans

ob = Solution()
words = ["xz", "xw", "y"]
s = "xyz"
print(ob.solve(words, s))

ইনপুট

["xz", "xw", "y"], "xyz"