Word Break for Senior Backend Engineer — Interview Guide

• dp[i] = true if s[0:i] can be segmented.
• Transition: dp[i] is true if some j < i has dp[j] true and s[j:i] is in the dictionary.
• A trie over the dictionary speeds up the substring lookup for large dictionaries.

def word_break(s, word_dict):
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]