Words Hidden in a Text

Medium

You are given a string text and a list words. A word is hidden in text if you can get it by crossing out some letters of text (possibly none) without reordering the rest. Return how many entries of words are hidden in text. If a word appears in the list several times, each occurrence counts separately.

Example 1

text='telegram', words=['tea', 'gram', 'late', 'tg', 'mart', 'ee'] → 4

"telegram" hides "tea" (t-e-…-a), "gram", "tg" and "ee". In "late" the t would have to come after the a, and in "mart" nothing follows the m.

Example 2

text='abc', words=['abc', 'abc', 'cba'] → 2

Repeated words are each counted; "cba" goes in reverse order and does not fit.

Example 3

text='zz', words=['zzz', 'z'] → 1

Constraints

1 ≤ len(text) ≤ 5·10⁴
1 ≤ len(words) ≤ 5000
1 ≤ len(words[i]) ≤ 50
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Array Hash Table String Binary Search Dynamic Programming Sorting

Similar problems

Split Into Dictionary Words Medium Most Searched Words Medium Word Grown Letter by Letter Medium Word Growth Chain Medium Weight by the Earliest Letter Medium

Input

text='telegram', words=['tea', 'gram', 'late', 'tg', 'mart', 'ee']

Expected

Run checks the first 3 tests in your browser. Submit checks all 58 tests on the server, hidden ones included.