19. Segment Query into Intents

Problem

A customer's raw query sometimes arrives as a single unspaced string — e.g. copy-pasted from a chat widget, or concatenated by an upstream parser. Given the raw string and a dictionary of known intent phrases (each phrase as a single joined token, e.g. "resetpassword", "checkorder"), you need two things: whether the query can be fully segmented into known phrases back-to-back, and every distinct way it can be segmented, so downstream NLU logic can consider each candidate parse.

This is two functions over the same underlying problem: can_segment is the classic Word Break I (a yes/no DP question), and all_segmentations is Word Break II (enumerate every valid parse). The order of the outer list returned by all_segmentations doesn't matter, but each inner list must read left-to-right. Return [] if the query can't be segmented at all.

Source: src/19_segment_query_intents.py

def can_segment(query: str, known_phrases: set[str]) -> bool: ...
def all_segmentations(query: str, known_phrases: set[str]) -> list[list[str]]: ...

>>> can_segment("resetpasswordhelp", {"reset", "password", "resetpassword", "help"})
True
>>> sorted(all_segmentations("resetpasswordhelp", {"reset", "password", "resetpassword", "help"}))
[['reset', 'password', 'help'], ['resetpassword', 'help']]
>>> can_segment("xyzunsegmentable", {"reset", "password"})
False

Step-by-Step Approach

1. can_segment (Word Break I): define dp[i] as "can query[:i] be fully segmented into known phrases". dp[0] = True (the empty prefix trivially segments).
2. For each end index i from 1 to len(query), set dp[i] = True if there's some split point j < i where dp[j] is already true and query[j:i] is a known phrase.
3. The answer is dp[n], whether the whole string is segmentable. This is O(n²) states, each doing an O(n) substring check (or O(1) with a hashed substring), so O(n³) or O(n²) total depending on substring handling.
4. all_segmentations (Word Break II): use top-down backtracking with memoization keyed by start index: backtrack(start) returns every way to segment query[start:].
5. Base case: start == len(query) means we've consumed the whole string — return [[]] (one way: the empty continuation), not [] (which would mean "no way").
6. Otherwise, try every end from start+1 to len(query); whenever query[start:end] is a known phrase, prepend it to every result of backtrack(end) and collect those into the results for start. Memoize by start so overlapping recursive calls aren't recomputed.

The key insight is that both functions share the same underlying recurrence — "can I reach position i, and by extension position n, through a chain of known-phrase splits" — but can_segment only needs a boolean DP table, while all_segmentations needs to actually reconstruct every path, which is why it uses backtracking with memoized partial results instead of a flat table.

Reference solution

def can_segment(query: str, known_phrases: set[str]) -> bool:
    # dp[i] = query[:i] is segmentable; O(n^2) states each checking a substring.
    n = len(query)
    # preallocate DP table, one slot per prefix length
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        # short-circuiting reachability check
        dp[i] = any(dp[j] and query[j:i] in known_phrases for j in range(i))
    return dp[n]


def all_segmentations(query: str, known_phrases: set[str]) -> list[list[str]]:
    # Top-down backtracking with memoization on start index (Word Break II).
    # cache backtrack(start) to avoid exponential recompute
    memo: dict[int, list[list[str]]] = {}

    # closure over query/known_phrases/memo
    def backtrack(start: int) -> list[list[str]]:
        if start == len(query):
            # one way to segment the empty remainder, not zero ways
            return [[]]
        if start in memo:
            return memo[start]
        results: list[list[str]] = []
        for end in range(start + 1, len(query) + 1):
            word = query[start:end]
            # O(1) average membership check via set hashing
            if word in known_phrases:
                for rest in backtrack(end):
                    # prepend word onto each recursive result
                    results.append([word] + rest)
        memo[start] = results
        return results

    return backtrack(0)

Key Functions & Tricks

• [False] * (n + 1) — preallocates the DP table, one bool per prefix length
• any(dp[j] and query[j:i] in known_phrases for j in range(i)) — short-circuiting generator reachability check
• query[j:i] / query[start:end] — string slicing to pull out candidate phrase chunks
• query[j:i] in known_phrases — O(1) average membership test via a set
• Nested function / closure (backtrack) — closes over query, known_phrases, memo without extra params
• Memoization dict keyed by start index — caches full result per start, avoids exponential blowup
• [[]] vs [] base case — [[]] means one (empty) way, letting the caller's loop still append [word]
• [word] + rest — list concatenation, prepends word onto the recursive result

How to Recognize This Pattern