- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a list of words and a string s, we have to find the number of strings in the words list that are subsequences of s.

So, if the input is like words = ["xz", "xw", "y"] s = "xyz", then the output will be 2, as "xz" and "y" are subsequences of "xyz".

To solve this, we will follow these steps −

- ans := 0
- d := an empty map
- for each word in words, do
- insert word at the end of d[word[0]]

- for each c in s, do
- l := d[c]
- d[c] := a new list
- for each word in l, do
- if size of word is 1, then
- ans := ans + 1

- otherwise,
- insert substring of word[from index 1 to end] at the end of d[word[1]]

- if size of word is 1, then

- return ans

Let us see the following implementation to get better understanding −

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

- Related Questions & Answers
- Program to count number of word concatenations are there in the list in python
- Program to find sum of digits that are inside one alphanumeric string in Python
- Python program to find word score from list of words
- Program to find length of subsequence that can be removed still t is subsequence of s in Python
- Program to find length of longest arithmetic subsequence of a given list in Python
- C++ Program to Find number of Ways to Partition a word such that each word is a Palindrome
- Program to find length of longest Fibonacci subsequence from a given list in Python
- Program to find length of longest alternating subsequence from a given list in Python
- Program to find length of longest balanced subsequence in Python
- Program to find length of longest anagram subsequence in Python
- Program to find length of longest increasing subsequence in Python
- Program to find length of longest palindromic subsequence in Python
- Program to find length of longest fibonacci subsequence in Python
- Program to find length of longest sign alternating subsequence from a list of numbers in Python
- Program to find closest subsequence sum in Python

Advertisements