main.cpp

// Source: https://leetcode.com/problems/word-break
// Title: Word Break
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.
//
// **Note** that the same word in the dictionary may be reused multiple times in the segmentation.
//
// **Example 1:**
//
// ```
// Input: s = "leetcode", wordDict = ["leet","code"]
// Output: true
// Explanation: Return true because "leetcode" can be segmented as "leet code".
// ```
//
// **Example 2:**
//
// ```
// Input: s = "applepenapple", wordDict = ["apple","pen"]
// Output: true
// Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
// Note that you are allowed to reuse a dictionary word.
// ```
//
// **Example 3:**
//
// ```
// Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
// Output: false
// ```
//
// **Constraints:**
//
// - `1 <= s.length <= 300`
// - `1 <= wordDict.length <= 1000`
// - `1 <= wordDict[i].length <= 20`
// - `s` and `wordDict[i]` consist of only lowercase English letters.
// - All the strings of `wordDict` are **unique**.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <vector>

using namespace std;

// Trie + DP
//
// DP[i] = true if s[:i] can be generated by the dictionary.
// For each i with DP[i] = true, traverse s[i:] in trie.
// Whenever we found a word (at index j), mark DP[j] true.
class Solution {
  struct Trie {
    struct Node {
      int children[26] = {};
      bool isWord = false;
    };

    vector<Node> nodes;

    Trie() : nodes(1) {}  // initialized with root node
    void reserve(int n) { nodes.reserve(n + 1); }

    void insert(const string& word) {
      int id = 0;
      for (const char ch : word) {
        int idx = ch - 'a';
        if (!nodes[id].children[idx]) {
          const int newId = nodes.size();
          nodes.emplace_back();
          nodes[id].children[idx] = newId;
        }
        id = nodes[id].children[idx];
      }
      nodes[id].isWord = true;
    }
  };

 public:
  bool wordBreak(const string& s, const vector<string>& wordDict) {
    const int n = s.size();

    // Build trie
    Trie trie;
    for (const auto word : wordDict) {
      trie.insert(word);
    }

    // DP
    auto dp = vector<int>(n + 1);
    dp[0] = true;
    for (int i = 0; i < n; ++i) {
      if (!dp[i]) continue;

      int id = 0;
      for (int j = i; j < n; ++j) {
        auto& nextId = trie.nodes[id].children[s[j] - 'a'];
        if (nextId == 0) break;
        id = nextId;
        if (trie.nodes[id].isWord) dp[j + 1] = true;
      }
    }

    return dp[n];
  }
};