Word Break

class TrieNode {
  public isWord: boolean;
  private readonly children: Record<string, TrieNode>;
  constructor() {
    this.isWord = false;
    this.children = {};
  }
 
  getChildNode(char: string): TrieNode {
    if (this.children[char]) {
      return this.children[char];
    }
    const newNode = new TrieNode();
    this.children[char] = newNode;
    return newNode;
  }
 
  hasChildNode(char: string) {
    return this.children[char] !== undefined;
  }
}
 
export function wordBreak(s: string, wordDict: string[]): boolean {
  const rootNode = new TrieNode();
  for (const word of wordDict) {
    let currentNode = rootNode;
    for (const char of word) {
      currentNode = currentNode.getChildNode(char);
    }
    currentNode.isWord = true;
  }
 
  const n = s.length;
  const dp = new Array<boolean>(n).fill(false);
  for (let i = 0; i < n; i++) {
    if (i === 0 || dp[i - 1]) {
      let currentNode = rootNode;
      for (let j = i; j < n; j++) {
        const char = s[j];
        if (!currentNode.hasChildNode(char)) {
          break;
        }
        currentNode = currentNode.getChildNode(char);
        if (currentNode.isWord) {
          dp[j] = true;
        }
      }
    }
  }
 
  return dp[n - 1];
}