499. Find the Toy
0
Medium
Alice loves a particular toy whose name is favToy.
Her mother tell her that she will only buy the favToy to Alice if she correctly answer her question.
Her mother gives a list of toy names toyList.
Alice have to find the number of toyList[i] that is a subsequence of favToy. Help Alice to get her favToy.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Her mother tell her that she will only buy the favToy to Alice if she correctly answer her question.
Her mother gives a list of toy names toyList.
Alice have to find the number of toyList[i] that is a subsequence of favToy. Help Alice to get her favToy.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
Input Format
First line of input contains a string favToy.
Second line of input contains a integer n number of toys in toyList.
Following n lines contains a string toy.
Second line of input contains a integer n number of toys in toyList.
Following n lines contains a string toy.
Output Format
Return an integer denoting number of toyList[i] that is a subsequence of favToy.
Example
Input
"abcde"
4
"a"
"bb"
"acd"
"ace"
Output
3
Constraints
1 <= favToy.length <= 5 * 10^4
1 <= toyList.length <= 5000
1 <= toyList[i].length <= 50
favToy and toyList[i] consist of only lowercase English letters.
1 <= toyList.length <= 5000
1 <= toyList[i].length <= 50
favToy and toyList[i] consist of only lowercase English letters.
Loading...
View Submissions
Console