Word Break

Medium Dynamic Programming

Given a string and a dictionary of words, decide whether the string can be segmented into a space-separated sequence of dictionary words. Bottom-up DP.

Sample input

s = "leetcode", dict = ["leet", "code"]

Sample output

true

Solution

def word_break(s, words):
    word_set = set(words)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[n]

print(word_break("leetcode", ["leet", "code"]))

function wordBreak(s, words) {
  const wordSet = new Set(words);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

console.log(wordBreak("leetcode", ["leet", "code"]));

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

public class Main {
    static boolean wordBreak(String s, List<String> words) {
        Set<String> wordSet = new HashSet<>(words);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(wordBreak("leetcode", List.of("leet", "code")));
    }
}

fun wordBreak(s: String, words: List<String>): Boolean {
    val wordSet = words.toHashSet()
    val n = s.length
    val dp = BooleanArray(n + 1)
    dp[0] = true
    for (i in 1..n) {
        for (j in 0 until i) {
            if (dp[j] && s.substring(j, i) in wordSet) {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

fun main() {
    println(wordBreak("leetcode", listOf("leet", "code")))
}

func wordBreak(_ s: String, _ words: [String]) -> Bool {
    let wordSet = Set(words)
    let chars = Array(s)
    let n = chars.count
    var dp = [Bool](repeating: false, count: n + 1)
    dp[0] = true
    for i in 1...n {
        for j in 0..<i {
            if dp[j] && wordSet.contains(String(chars[j..<i])) {
                dp[i] = true
                break
            }
        }
    }
    return dp[n]
}

print(wordBreak("leetcode", ["leet", "code"]))

bool wordBreak(String s, List<String> words) {
  final wordSet = words.toSet();
  final n = s.length;
  final dp = List.filled(n + 1, false);
  dp[0] = true;
  for (var i = 1; i <= n; i++) {
    for (var j = 0; j < i; j++) {
      if (dp[j] && wordSet.contains(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

void main() {
  print(wordBreak("leetcode", ["leet", "code"]));
}

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

bool wordBreak(const string& s, const vector<string>& words) {
    unordered_set<string> wordSet(words.begin(), words.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

int main() {
    cout << (wordBreak("leetcode", {"leet", "code"}) ? "true" : "false") << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

int main() {
    const char *s = "leetcode";
    const char *dict[] = {"leet", "code"};
    int dictSize = 2;
    int n = strlen(s);
    int dp[100] = {0};
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                int len = i - j;
                for (int w = 0; w < dictSize; w++) {
                    if ((int) strlen(dict[w]) == len && strncmp(s + j, dict[w], len) == 0) {
                        dp[i] = 1;
                        break;
                    }
                }
            }
            if (dp[i]) break;
        }
    }
    printf("%s\n", dp[n] ? "true" : "false");
    return 0;
}