139. Word break

139_solution1.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// C has no built-in hash set, so check the piece against each word
static bool inDict(const char *piece, int len, char **wordDict,
                   int wordDictSize) {
  for (int k = 0; k < wordDictSize; k++) {
    if ((int)strlen(wordDict[k]) == len &&
        strncmp(piece, wordDict[k], len) == 0)
      return true;
  }
  return false;
}

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
  int n = strlen(s);
  bool *dp = calloc(n + 1, sizeof(bool));
  dp[0] = true; // empty prefix is segmentable

  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
      if (dp[j] && inDict(s + j, i - j, wordDict, wordDictSize)) {
        dp[i] = true;
        break; // one valid split is enough
      }
    }
  }
  bool res = dp[n];
  free(dp);
  return res;
}

139_solution2.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

// C has no built-in hash set, so check the piece against each word
static bool inDict(const char *piece, int len, char **wordDict,
                   int wordDictSize) {
  for (int k = 0; k < wordDictSize; k++) {
    if ((int)strlen(wordDict[k]) == len &&
        strncmp(piece, wordDict[k], len) == 0)
      return true;
  }
  return false;
}

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
  int n = strlen(s);

  int maxLen = 0;
  for (int k = 0; k < wordDictSize; k++) {
    int len = strlen(wordDict[k]);
    if (len > maxLen)
      maxLen = len;
  }

  bool *dp = calloc(n + 1, sizeof(bool));
  dp[0] = true;

  for (int i = 1; i <= n; i++) {
    // A piece longer than maxLen can't be a word, so start j no earlier than
    // i - maxLen
    for (int j = i - maxLen > 0 ? i - maxLen : 0; j < i; j++) {
      if (dp[j] && inDict(s + j, i - j, wordDict, wordDictSize)) {
        dp[i] = true;
        break;
      }
    }
  }
  bool res = dp[n];
  free(dp);
  return res;
}

139_solution3.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
  int n = strlen(s);
  bool *dp = calloc(n + 1, sizeof(bool));
  dp[0] = true;

  for (int i = 1; i <= n; i++) {
    for (int k = 0; k < wordDictSize; k++) {
      int len = strlen(wordDict[k]);
      // Does word k end exactly at position i?
      if (len <= i && dp[i - len] &&
          strncmp(s + i - len, wordDict[k], len) == 0) {
        dp[i] = true;
        break;
      }
    }
  }
  bool res = dp[n];
  free(dp);
  return res;
}

139_solution4.c

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

typedef struct TrieNode {
  struct TrieNode *children[26];
  bool isWord;
} TrieNode;

static void freeTrie(TrieNode *node) {
  if (!node)
    return;
  for (int c = 0; c < 26; c++)
    freeTrie(node->children[c]);
  free(node);
}

bool wordBreak(char *s, char **wordDict, int wordDictSize) {
  // Build the trie from the dictionary
  TrieNode *root = calloc(1, sizeof(TrieNode));
  for (int w = 0; w < wordDictSize; w++) {
    TrieNode *node = root;
    for (char *c = wordDict[w]; *c; c++) {
      if (!node->children[*c - 'a'])
        node->children[*c - 'a'] = calloc(1, sizeof(TrieNode));
      node = node->children[*c - 'a'];
    }
    node->isWord = true;
  }

  int n = strlen(s);
  bool *dp = calloc(n + 1, sizeof(bool));
  dp[0] = true;

  for (int j = 0; j < n; j++) {
    if (!dp[j])
      continue; // only start a word where the prefix is segmentable

    // Walk s and the trie together, starting at j
    TrieNode *node = root;
    for (int k = j; k < n; k++) {
      node = node->children[s[k] - 'a'];
      if (!node)
        break; // no dictionary word continues this way
      if (node->isWord)
        dp[k + 1] = true; // s[j..k] is a word, so the first k+1 chars are segmentable
    }
  }
  bool res = dp[n];
  free(dp);
  freeTrie(root);
  return res;
}

139_solution1.cpp

#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
  bool wordBreak(string s, vector<string> &wordDict) {
    int n = s.size();
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    vector<bool> dp(n + 1, false);
    dp[0] = true; // empty prefix is segmentable

    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < i; j++) {
        if (dp[j] && words.count(s.substr(j, i - j))) {
          dp[i] = true;
          break; // one valid split is enough
        }
      }
    }
    return dp[n];
  }
};

139_solution2.cpp

#include <algorithm>
#include <string>
#include <unordered_set>
#include <vector>

using namespace std;

class Solution {
public:
  bool wordBreak(string s, vector<string> &wordDict) {
    int n = s.size();
    unordered_set<string> words(wordDict.begin(), wordDict.end());

    int maxLen = 0;
    for (auto &w : wordDict)
      maxLen = max(maxLen, (int)w.size());

    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
      // A piece longer than maxLen can't be a word, so start j no earlier than
      // i - maxLen
      for (int j = max(0, i - maxLen); j < i; j++) {
        if (dp[j] && words.count(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[n];
  }
};

139_solution3.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
  bool wordBreak(string s, vector<string> &wordDict) {
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
      for (auto &w : wordDict) {
        int len = w.size();
        // Does word w end exactly at position i?
        if (len <= i && dp[i - len] && s.compare(i - len, len, w) == 0) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[n];
  }
};

139_solution4.cpp

#include <string>
#include <vector>

using namespace std;

class Solution {
  struct TrieNode {
    TrieNode *children[26] = {};
    bool isWord = false;
  };

public:
  bool wordBreak(string s, vector<string> &wordDict) {
    // Build the trie from the dictionary
    TrieNode *root = new TrieNode();
    for (auto &w : wordDict) {
      TrieNode *node = root;
      for (char c : w) {
        if (!node->children[c - 'a'])
          node->children[c - 'a'] = new TrieNode();
        node = node->children[c - 'a'];
      }
      node->isWord = true;
    }

    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int j = 0; j < n; j++) {
      if (!dp[j])
        continue; // only start a word where the prefix is segmentable

      // Walk s and the trie together, starting at j
      TrieNode *node = root;
      for (int k = j; k < n; k++) {
        node = node->children[s[k] - 'a'];
        if (!node)
          break; // no dictionary word continues this way
        if (node->isWord)
          dp[k + 1] =
              true; // s[j..k] is a word, so the first k+1 chars are segmentable
      }
    }
    return dp[n];
  }
};

139_solution1.go

package dp

func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    words := make(map[string]bool, len(wordDict))
    for _, w := range wordDict {
        words[w] = true
    }
    dp := make([]bool, n+1)
    dp[0] = true // empty prefix is segmentable

    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && words[s[j:i]] {
                dp[i] = true
                break // one valid split is enough
            }
        }
    }
    return dp[n]
}

139_solution2.go

package dp

func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    words := make(map[string]bool, len(wordDict))
    maxLen := 0
    for _, w := range wordDict {
        words[w] = true
        maxLen = max(maxLen, len(w))
    }

    dp := make([]bool, n+1)
    dp[0] = true

    for i := 1; i <= n; i++ {
        // A piece longer than maxLen can't be a word, so start j no earlier than
        // i - maxLen
        for j := max(0, i-maxLen); j < i; j++ {
            if dp[j] && words[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

139_solution3.go

package dp

func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for i := 1; i <= n; i++ {
        for _, w := range wordDict {
            l := len(w)
            // Does word w end exactly at position i?
            if l <= i && dp[i-l] && s[i-l:i] == w {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

139_solution4.go

package dp

type trieNode struct {
    children [26]*trieNode
    isWord   bool
}

func wordBreak(s string, wordDict []string) bool {
    // Build the trie from the dictionary
    root := &trieNode{}
    for _, w := range wordDict {
        node := root
        for i := 0; i < len(w); i++ {
            c := w[i] - 'a'
            if node.children[c] == nil {
                node.children[c] = &trieNode{}
            }
            node = node.children[c]
        }
        node.isWord = true
    }

    n := len(s)
    dp := make([]bool, n+1)
    dp[0] = true

    for j := 0; j < n; j++ {
        if !dp[j] {
            continue // only start a word where the prefix is segmentable
        }

        // Walk s and the trie together, starting at j
        node := root
        for k := j; k < n; k++ {
            node = node.children[s[k]-'a']
            if node == nil {
                break // no dictionary word continues this way
            }
            if node.isWord {
                dp[k+1] = true // s[j..k] is a word, so the first k+1 chars are segmentable
            }
        }
    }
    return dp[n]
}

139_solution1.java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> words = new HashSet<>(wordDict);
        boolean[] dp = new boolean[n + 1];
        dp[0] = true; // empty prefix is segmentable

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break; // one valid split is enough
                }
            }
        }
        return dp[n];
    }
}

139_solution2.java

import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        Set<String> words = new HashSet<>(wordDict);

        int maxLen = 0;
        for (String w : wordDict)
            maxLen = Math.max(maxLen, w.length());

        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            // A piece longer than maxLen can't be a word, so start j no earlier than
            // i - maxLen
            for (int j = Math.max(0, i - maxLen); j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

139_solution3.java

import java.util.List;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (String w : wordDict) {
                int len = w.length();
                // Does word w end exactly at position i?
                if (len <= i && dp[i - len] && s.startsWith(w, i - len)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

139_solution4.java

import java.util.List;

class Solution {
    private static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isWord = false;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        // Build the trie from the dictionary
        TrieNode root = new TrieNode();
        for (String w : wordDict) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.children[c - 'a'] == null)
                    node.children[c - 'a'] = new TrieNode();
                node = node.children[c - 'a'];
            }
            node.isWord = true;
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int j = 0; j < n; j++) {
            if (!dp[j])
                continue; // only start a word where the prefix is segmentable

            // Walk s and the trie together, starting at j
            TrieNode node = root;
            for (int k = j; k < n; k++) {
                node = node.children[s.charAt(k) - 'a'];
                if (node == null)
                    break; // no dictionary word continues this way
                if (node.isWord)
                    dp[k + 1] = true; // s[j..k] is a word, so the first k+1 chars are segmentable
            }
        }
        return dp[n];
    }
}

139_solution1.js

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length;
  const words = new Set(wordDict);
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // empty prefix is segmentable

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.substring(j, i))) {
        dp[i] = true;
        break; // one valid split is enough
      }
    }
  }
  return dp[n];
};

139_solution2.js

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length;
  const words = new Set(wordDict);

  let maxLen = 0;
  for (const w of wordDict) maxLen = Math.max(maxLen, w.length);

  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= n; i++) {
    // A piece longer than maxLen can't be a word, so start j no earlier than
    // i - maxLen
    for (let j = Math.max(0, i - maxLen); j < i; j++) {
      if (dp[j] && words.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
};

139_solution3.js

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  for (let i = 1; i <= n; i++) {
    for (const w of wordDict) {
      const len = w.length;
      // Does word w end exactly at position i?
      if (len <= i && dp[i - len] && s.startsWith(w, i - len)) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
};

139_solution4.js

class TrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isWord = false;
  }
}

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const idx = (c) => c.charCodeAt(0) - 97;

  // Build the trie from the dictionary
  const root = new TrieNode();
  for (const w of wordDict) {
    let node = root;
    for (const c of w) {
      if (!node.children[idx(c)]) node.children[idx(c)] = new TrieNode();
      node = node.children[idx(c)];
    }
    node.isWord = true;
  }

  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  for (let j = 0; j < n; j++) {
    if (!dp[j]) continue; // only start a word where the prefix is segmentable

    // Walk s and the trie together, starting at j
    let node = root;
    for (let k = j; k < n; k++) {
      node = node.children[idx(s[k])];
      if (!node) break; // no dictionary word continues this way
      if (node.isWord) dp[k + 1] = true; // s[j..k] is a word, so the first k+1 chars are segmentable
    }
  }
  return dp[n];
};

139_solution1.py

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        words = set(wordDict)
        dp = [False] * (n + 1)
        dp[0] = True  # empty prefix is segmentable

        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break  # one valid split is enough
        return dp[n]

139_solution2.py

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        words = set(wordDict)
        max_len = max(len(w) for w in wordDict)

        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            # A piece longer than max_len can't be a word, so start j no earlier
            # than i - max_len
            for j in range(max(0, i - max_len), i):
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break
        return dp[n]

139_solution3.py

from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for i in range(1, n + 1):
            for w in wordDict:
                length = len(w)
                # Does word w end exactly at position i?
                if length <= i and dp[i - length] and s.startswith(w, i - length):
                    dp[i] = True
                    break
        return dp[n]

139_solution4.py

from typing import List


class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Build the trie from the dictionary
        root = TrieNode()
        for w in wordDict:
            node = root
            for c in w:
                node = node.children.setdefault(c, TrieNode())
            node.is_word = True

        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for j in range(n):
            if not dp[j]:
                continue  # only start a word where the prefix is segmentable

            # Walk s and the trie together, starting at j
            node = root
            for k in range(j, n):
                node = node.children.get(s[k])
                if node is None:
                    break  # no dictionary word continues this way
                if node.is_word:
                    dp[k + 1] = True  # s[j..k] is a word, so the first k+1 chars are segmentable
        return dp[n]

139_solution1.rs

use std::collections::HashSet;

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let n = s.len();
        let words: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
        let mut dp = vec![false; n + 1];
        dp[0] = true; // empty prefix is segmentable

        for i in 1..=n {
            for j in 0..i {
                if dp[j] && words.contains(&s[j..i]) {
                    dp[i] = true;
                    break; // one valid split is enough
                }
            }
        }
        dp[n]
    }
}

139_solution2.rs

use std::collections::HashSet;

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let n = s.len();
        let words: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
        let max_len = word_dict.iter().map(|w| w.len()).max().unwrap_or(0);

        let mut dp = vec![false; n + 1];
        dp[0] = true;

        for i in 1..=n {
            // A piece longer than max_len can't be a word, so start j no earlier
            // than i - max_len
            for j in i.saturating_sub(max_len)..i {
                if dp[j] && words.contains(&s[j..i]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        dp[n]
    }
}

139_solution3.rs

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        let n = s.len();
        let mut dp = vec![false; n + 1];
        dp[0] = true;

        for i in 1..=n {
            for w in &word_dict {
                let len = w.len();
                // Does word w end exactly at position i?
                if len <= i && dp[i - len] && &s[i - len..i] == w {
                    dp[i] = true;
                    break;
                }
            }
        }
        dp[n]
    }
}

139_solution4.rs

#[derive(Default)]
struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_word: bool,
}

impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> bool {
        // Build the trie from the dictionary
        let mut root = TrieNode::default();
        for w in &word_dict {
            let mut node = &mut root;
            for c in w.bytes() {
                node = node.children[(c - b'a') as usize].get_or_insert_with(Default::default);
            }
            node.is_word = true;
        }

        let b = s.as_bytes();
        let n = b.len();
        let mut dp = vec![false; n + 1];
        dp[0] = true;

        for j in 0..n {
            if !dp[j] {
                continue; // only start a word where the prefix is segmentable
            }

            // Walk s and the trie together, starting at j
            let mut node = &root;
            for k in j..n {
                match &node.children[(b[k] - b'a') as usize] {
                    Some(next) => node = next,
                    None => break, // no dictionary word continues this way
                }
                if node.is_word {
                    dp[k + 1] = true; // s[j..k] is a word, so the first k+1 chars are segmentable
                }
            }
        }
        dp[n]
    }
}