Split a query into known words

Scenario

A store's search box receives queries typed without spaces, such as a voice note turned into text. The search team keeps a list of known words. A query is easy to understand when it can be cut into known words, one after another, with nothing left over. A known word may be used more than once.

Your team lead asks: "Can this query be split into known words?"

Your task

Write can_split(query, words).

query is a string of lowercase letters. words is a list of known lowercase words.
Cut query into pieces from left to right, with no letters left over, so that every piece is a known word. A known word may be used any number of times.
Return True if some way of cutting works, and False otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  query = "tablelamp", words = ["tab", "table", "lamp", "lam", "p", "le"]
Output: true

Let ok[i] say whether the first i letters can be split into known words. The empty start can, so ok[0] is true.

For each i, try every last word. It starts at j and ends at i. It works when ok[j] is true and the letters from j to i are a known word.

i	First i letters	A last word that works	ok[i]
0	(empty)	the start	true
1	t	none	false
2	ta	none	false
3	tab	tab, after ok[0]	true
4	tabl	none: l is not a word	false
5	table	table, after ok[0]	true
6	tablel	none	false
7	tablela	none	false
8	tablelam	lam, after ok[5]	true
9	tablelamp	lamp, after ok[5]	true

The answer is ok[9] = true: for example table and lamp.

Example 2#

text2 lines

Input:  query = "aaab", words = ["a", "aa"]
Output: false

No known word contains the letter b, so the last letter can never be covered.

Example 3#

text2 lines

Input:  query = "ababab", words = ["ab"]
Output: true

The word ab is used three times. A known word can be used again.

Constraints

1 ≤ len(query) ≤ 2000, lowercase letters only
1 ≤ len(words) ≤ 1000, and each word has 1 to 20 lowercase letters

What does n ≤ 2000 tell you?

The query has up to 2,000 letters. The number of ways to cut a run of letters into pieces doubles with almost every letter, so trying every cut never finishes. A table with one answer for each of the 2,001 positions, with at most 20 pieces to try at each, is about 40,000 checks.

Scenario

Your team lead asks: "Can this query be split into known words?"

Your task

Write can_split(query, words).

query is a string of lowercase letters. words is a list of known lowercase words.
Cut query into pieces from left to right, with no letters left over, so that every piece is a known word. A known word may be used any number of times.
Return True if some way of cutting works, and False otherwise.

Examples

Example 1 (traced)#

text2 lines

Input:  query = "tablelamp", words = ["tab", "table", "lamp", "lam", "p", "le"]
Output: true

Let ok[i] say whether the first i letters can be split into known words. The empty start can, so ok[0] is true.

For each i, try every last word. It starts at j and ends at i. It works when ok[j] is true and the letters from j to i are a known word.

i	First i letters	A last word that works	ok[i]
0	(empty)	the start	true
1	t	none	false
2	ta	none	false
3	tab	tab, after ok[0]	true
4	tabl	none: l is not a word	false
5	table	table, after ok[0]	true
6	tablel	none	false
7	tablela	none	false
8	tablelam	lam, after ok[5]	true
9	tablelamp	lamp, after ok[5]	true

The answer is ok[9] = true: for example table and lamp.

Example 2#

text2 lines

Input:  query = "aaab", words = ["a", "aa"]
Output: false

No known word contains the letter b, so the last letter can never be covered.

Example 3#

text2 lines

Input:  query = "ababab", words = ["ab"]
Output: true

The word ab is used three times. A known word can be used again.

Constraints

1 ≤ len(query) ≤ 2000, lowercase letters only
1 ≤ len(words) ≤ 1000, and each word has 1 to 20 lowercase letters

What does n ≤ 2000 tell you?