वर्ड लिस्ट में मौजूद सबसीक्वेंस की संख्या ज्ञात करने का पायथन प्रोग्राम

मान लीजिए हमारे पास शब्दों की एक सूची और एक स्ट्रिंग s है, हमें शब्दों की सूची में उन स्ट्रिंग्स की संख्या ढूंढनी है जो s के सबसीक्वेंस हैं।

उदाहरण के लिए, यदि इनपुट words = ["xz", "xw", "y"] s = "xyz" है, तो आउटपुट 2 होगा, क्योंकि "xz" और "y" "xyz" के सबसीक्वेंस हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

• ans := 0
• d := एक खाली मैप
• प्रत्येक word के लिए words में, करें
  • word को d[word[0]] के अंत में डालें
• प्रत्येक c के लिए s में, करें
  • l := d[c]
  • d[c] := एक नई सूची
  • प्रत्येक word के लिए l में, करें
    • यदि word का आकार 1 है, तो
      • ans := ans + 1
    • अन्यथा,
      • word[1 से अंत तक] के सबस्ट्रिंग को 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"

आउटपुट

2