Word Break

Lesson 14 of 14 in Coddy's Tries - Data Structures Series #8 course.

Given a string s and a dictionary of words, can we chop s into a sequence of dictionary words with nothing left over? "leetcode" breaks as "leet" + "code" if both are in the dictionary; "catsandog" does not break no matter how we cut it.

A dynamic-programming pass nails it. Define dp[i] as can the first i characters be segmented? Start with dp[0] = true. For every i where dp[i] is true, walk the trie from position i in the string; every time the walk lands on an isEndOfWord node at index j, set dp[j+1] = true.

The trie makes each walk fast: a single missing character ends it. The final answer lives in dp[n].

Challenge

Medium

Write a function wordBreak that gets a string s and a string array dictionary, and returns true if s can be split into one or more whitespace-free pieces that are all in the dictionary, or false otherwise.

An empty s is always breakable.

You must use the Trie class (provided in trie along with trienode) - do not use language built-ins like sets, dicts, or maps to count/track.

Try it yourself

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"

int main() {
    char s[4096], dLine[4096];
    if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
    if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
    s[strcspn(s, "\r\n")] = '\0';
    dLine[strcspn(dLine, "\r\n")] = '\0';
    char* d[1024]; int dn = 0;
    char* tok = strtok(dLine, " \t");
    while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
    printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
    return 0;
}

All lessons in Tries - Data Structures Series #8

1Introduction

Introduction What is a Trie?

2Trie Project

TrieNode Class Trie Class Insert Search StartsWith Delete WordCount

3Practice Challenges

Longest Common Prefix Count Words With Prefix Autocomplete Longest Word In DictWord Break