Squashed Hashtag

Mediumdynamic programmingAlso known as Word Break

A screen reader reads posts aloud for people who cannot see the screen. Hashtags are a problem: #lemoncakerecipe is one long run of letters, and reading it letter by letter is useless. The reader has a list of known words and tries to cut each hashtag into them, so it can say "lemon cake recipe".

Before trying to say anything, it needs to know whether a clean cut exists at all.

Your task

Write canSplit(tag, words). Return true if tag can be cut into pieces so that every piece is in words, and false otherwise.

Every letter must belong to exactly one piece, and pieces keep their order. A word can be used any number of times. The tag has no # and is all lowercase.

canSplit(tag: string, words: string[]) → bool

Examples

Example 1

Input

tag = "lemoncakerecipe"
words = ["cake", "lemon", "recipe", "rec", "ipe"]

Output

true

Why

Example 2

Input

tag = "startupweek"
words = ["star", "start", "up", "week"]

Output

true

Why

start | up | week works. Grabbing the shortest word first takes "star" and leaves "tupweek", which nothing fits. So you must be ready to try a different first word.

Example 3

Input

tag = "nightowls"
words = ["night", "owl", "nigh", "towel"]

Output

false

Why

night | owl leaves a lone "s". nigh leaves "towls", and "towel" does not match it. No cut covers every letter.

Constraints

1 ≤ tag.length ≤ 300
1 ≤ words.length ≤ 1,000
1 ≤ words[i].length ≤ 20, all words different
tag and words contain only lowercase letters a to z.

Start with brute force

Try every word that matches the start of the tag, then recursively do the same on what is left. Backtrack when you get stuck.

On a tag like forty as followed by a b, with words a, aa, aaa, every split of the as is tried before the recursion learns that the b can never be covered. That is billions of splits. The recursion keeps asking "can the rest from position 20 be cut?" again and again, and the answer never changes.

Hints

0 of 4 shown

Hint 1
In startupweek, suppose you already know that the first 7 letters, startup, can be cut cleanly. What is the only thing left to check for the whole tag?
Hint 2
The rest, week, must be one word. More generally: the first i letters can be cut if, for some earlier point j, the first j letters can be cut and the letters from j to i form one word.
Hint 3
Keep a list ok where ok[i] says whether the first i letters can be cut. ok[0] is true: the empty start needs no words. Fill it from left to right.
Hint 4
For each i, try only the last-word lengths from 1 to 20 (no word is longer). If ok[i - len] is true and tag.slice(i - len, i) is in a set of the words, mark ok[i] true. The answer is ok[tag.length].

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Whatever the cut, it has a last word. If the last word covers letters j to i, then the first j letters must be cuttable on their own. So ok[i] is true when some ok[j] is true and tag[j..i) is a word.

Trace startupweek with words star, start, up, week. Positions are letter counts:

ok[0] = true (empty start).
ok[4]: "star" is a word and ok[0] is true, so true.
ok[5]: "start" is a word and ok[0] is true, so true.
ok[6]: the true spots so far are 0, 4 and 5, so the last word would be "startu", "tu" or "u". None are words. False.
ok[7]: "up" follows ok[5], true. (From ok[4] the rest would be "tup", not a word.)
ok[11]: "week" follows ok[7], true. Answer true.

Unlike the greedy tries, the table keeps every reachable cut point at once, so a dead end after "star" costs nothing: "start" is already recorded.

Reference solution

function canSplit(tag, words) {
  const known = new Set(words);
  let longest = 0;
  for (const w of words) longest = Math.max(longest, w.length);
  // ok[i] = can the first i letters be cut into known words?
  const ok = new Array(tag.length + 1).fill(false);
  ok[0] = true;
  for (let i = 1; i <= tag.length; i++) {
    for (let len = 1; len <= longest && len <= i && !ok[i]; len++) {
      // the last word is tag[i - len .. i)
      if (ok[i - len] && known.has(tag.slice(i - len, i))) ok[i] = true;
    }
  }
  return ok[tag.length];
}

def can_split(tag, words):
    known = set(words)
    longest = max(len(w) for w in words)
    # ok[i] = can the first i letters be cut into known words?
    ok = [True] + [False] * len(tag)
    for i in range(1, len(tag) + 1):
        for length in range(1, min(longest, i) + 1):
            # the last word is tag[i - length : i]
            if ok[i - length] and tag[i - length:i] in known:
                ok[i] = True
                break
    return ok[len(tag)]

TimeO(n × L²)For each of the n positions, up to L word lengths, and each slice and hash costs up to L (L ≤ 20).

SpaceO(n + total letters in words)The ok table plus the word set.

Learn the idea: DP on Strings 1D Dynamic Programming Hash Tables

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code