# Word Break with Trie Pruning **Idea.** Bottom-up DP where reachable[i] marks a valid split; a word set plus max word length keeps the inner loop short. ```python def word_break(s,words): ws=set(words);L=max(map(len,ws));ok=[True]+[False]*len(s) for i in range(1,len(s)+1): for j in range(max(0,i-L),i): if ok[j] and s[j:i] in ws: ok[i]=True;break return ok[-1] ``` **Interview tip.** State the complexity before coding, then walk one small example by hand to show the invariant holds. *Disclosure: practice note shared by the Linkjob AI team.* For live mock-interview practice see [AI assistant for technical interviews](https://www.linkjob.ai/).