Skip to content

Word Combinations

  • Title: Word Combinations
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/1731
  • Secondary topics: DP on suffixes, Dictionary segmentation, Duplicate words
  • Difficulty: medium
  • Subtype: Count how many dictionary segmentations form the target string
  • Status: solved
  • Solution file: wordcombinations.cpp

Why Practice This

This is a strong trie problem because the trie is not the whole answer by itself. The real structure is:

  • DP decides what state to count
  • the trie makes each DP transition cheap enough to enumerate

That split is exactly why this problem is worth learning.

Recognition Cue

Reach for trie + DP when:

  • the target is one long string
  • the dictionary contains many overlapping prefixes
  • the answer counts or optimizes segmentations, not only yes/no membership
  • checking every word at every position feels too wasteful

The strongest smell is:

  • "for each starting index, many dictionary words may match here"

That is where the trie prunes the candidate set and DP counts the rest.

Problem-Specific Transformation

The statement sounds like pure dictionary matching, but the reusable rewrite is:

  • DP state = number of ways to finish from one starting index
  • trie = fast way to enumerate exactly the dictionary words that begin there

So the whole task becomes:

  • walk the target from position i
  • follow trie edges as long as possible
  • every terminal node contributes one DP transition

The trie is therefore a transition generator, not the answer by itself.

Core Idea

Let dp[i] be the number of ways to split the suffix s[i..n-1] into dictionary words.

Then:

  • dp[n] = 1 because the empty suffix has one valid completion
  • for each position i, we try every dictionary word that starts at i

Naively, that means checking all words against s[i..], which is too wasteful.

Instead, insert all dictionary words into a trie. Then for a fixed start i, walk forward through the text:

s[i], s[i + 1], s[i + 2], ...

and move through the trie at the same time.

Whenever the current trie node is terminal, we found one dictionary word ending at j, so it contributes:

dp[j + 1]

to dp[i].

If the next text character has no trie edge, we stop immediately. So each DP state only explores prefixes that are actually present in the dictionary.

The solution computes dp from right to left so every dp[j + 1] is already known when needed.

Complexity

  • building the trie: O(total dictionary length)
  • DP transitions: O(total successful trie walks from all start positions)
  • worst-case bound: O(n * longest_word_length + total dictionary length)

This is fast enough for the intended constraints when implemented iteratively.

Pitfalls / Judge Notes

  • The answer is modulo 10^9 + 7.
  • A trie node should track terminal multiplicity, not just a boolean, if duplicate words are allowed in the input.
  • Compute dp from right to left so transitions point to already-computed states.
  • Stop the forward scan immediately when the trie has no next edge for the current character.

Reusable Pattern

  • Topic page: Trie
  • Practice ladder: Trie ladder
  • Starter template: trie-basic.cpp
  • Notebook refresher: String cheatsheet
  • Carry forward: use the trie only for the shared-prefix part; keep the extra DP or query logic separate.
  • This note adds: the state transition or counting rule built on top of the trie.

Solutions