LeetCode 0139. Word Break Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

Description

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.

Solutions

Solution 1

PythonJavaC++GoTypeScriptRustC#

class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) n = len(s) f = [True] + [False] * n for i in range(1, n + 1): f[i] = any(f[j] and s[j:i] in words for j in range(i)) return f[n](code-box)

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> words = new HashSet<>(wordDict); int n = s.length(); boolean[] f = new boolean[n + 1]; f[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (f[j] && words.contains(s.substring(j, i))) { f[i] = true; break; } } } return f[n]; } }(code-box)

class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> words(wordDict.begin(), wordDict.end()); int n = s.size(); bool f[n + 1]; memset(f, false, sizeof(f)); f[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (f[j] && words.count(s.substr(j, i - j))) { f[i] = true; break; } } } return f[n]; } };(code-box)

func wordBreak(s string, wordDict []string) bool { words := map[string]bool{} for _, w := range wordDict { words[w] = true } n := len(s) f := make([]bool, n+1) f[0] = true for i := 1; i <= n; i++ { for j := 0; j < i; j++ { if f[j] && words[s[j:i]] { f[i] = true break } } } return f[n] }(code-box)

function wordBreak(s: string, wordDict: string[]): boolean { const words = new Set(wordDict); const n = s.length; const f: boolean[] = new Array(n + 1).fill(false); f[0] = true; for (let i = 1; i <= n; ++i) { for (let j = 0; j < i; ++j) { if (f[j] && words.has(s.substring(j, i))) { f[i] = true; break; } } } return f[n]; }(code-box)

impl Solution { pub fn word_break(s: String, word_dict: Vec<String>) -> bool { let words: std::collections::HashSet<String> = word_dict.into_iter().collect(); let mut f = vec![false; s.len() + 1]; f[0] = true; for i in 1..=s.len() { for j in 0..i { f[i] |= f[j] && words.contains(&s[j..i]); } } f[s.len()] } }(code-box)

public class Solution { public bool WordBreak(string s, IList<string> wordDict) { var words = new HashSet<string>(wordDict); int n = s.Length; var f = new bool[n + 1]; f[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (f[j] && words.Contains(s.Substring(j, i - j))) { f[i] = true; break; } } } return f[n]; } }(code-box)

Solution 2

PythonJavaC++GoTypeScriptC#

class Trie: def __init__(self): self.children: List[Trie | None] = [None] * 26 self.isEnd = False def insert(self, w: str): node = self for c in w: idx = ord(c) - ord('a') if not node.children[idx]: node.children[idx] = Trie() node = node.children[idx] node.isEnd = True class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: trie = Trie() for w in wordDict: trie.insert(w) n = len(s) f = [False] * (n + 1) f[n] = True for i in range(n - 1, -1, -1): node = trie for j in range(i, n): idx = ord(s[j]) - ord('a') if not node.children[idx]: break node = node.children[idx] if node.isEnd and f[j + 1]: f[i] = True break return f[0](code-box)

class Solution { public boolean wordBreak(String s, List<String> wordDict) { Trie trie = new Trie(); for (String w : wordDict) { trie.insert(w); } int n = s.length(); boolean[] f = new boolean[n + 1]; f[n] = true; for (int i = n - 1; i >= 0; --i) { Trie node = trie; for (int j = i; j < n; ++j) { int k = s.charAt(j) - 'a'; if (node.children[k] == null) { break; } node = node.children[k]; if (node.isEnd && f[j + 1]) { f[i] = true; break; } } } return f[0]; } } class Trie { Trie[] children = new Trie[26]; boolean isEnd = false; public void insert(String w) { Trie node = this; for (int i = 0; i < w.length(); ++i) { int j = w.charAt(i) - 'a'; if (node.children[j] == null) { node.children[j] = new Trie(); } node = node.children[j]; } node.isEnd = true; } }(code-box)

class Trie { public: vector<Trie*> children; bool isEnd; Trie() : children(26) , isEnd(false) {} void insert(string word) { Trie* node = this; for (char c : word) { c -= 'a'; if (!node->children[c]) node->children[c] = new Trie(); node = node->children[c]; } node->isEnd = true; } }; class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { Trie trie; for (auto& w : wordDict) { trie.insert(w); } int n = s.size(); vector<bool> f(n + 1); f[n] = true; for (int i = n - 1; ~i; --i) { Trie* node = &trie; for (int j = i; j < n; ++j) { int k = s[j] - 'a'; if (!node->children[k]) { break; } node = node->children[k]; if (node->isEnd && f[j + 1]) { f[i] = true; break; } } } return f[0]; } };(code-box)

type trie struct { children [26]*trie isEnd bool } func newTrie() *trie { return &trie{} } func (t *trie) insert(w string) { node := t for _, c := range w { c -= 'a' if node.children[c] == nil { node.children[c] = newTrie() } node = node.children[c] } node.isEnd = true } func wordBreak(s string, wordDict []string) bool { trie := newTrie() for _, w := range wordDict { trie.insert(w) } n := len(s) f := make([]bool, n+1) f[n] = true for i := n - 1; i >= 0; i-- { node := trie for j := i; j < n; j++ { k := s[j] - 'a' if node.children[k] == nil { break } node = node.children[k] if node.isEnd && f[j+1] { f[i] = true break } } } return f[0] }(code-box)

function wordBreak(s: string, wordDict: string[]): boolean { const trie = new Trie(); for (const w of wordDict) { trie.insert(w); } const n = s.length; const f: boolean[] = new Array(n + 1).fill(false); f[n] = true; for (let i = n - 1; i >= 0; --i) { let node: Trie = trie; for (let j = i; j < n; ++j) { const k = s.charCodeAt(j) - 97; if (!node.children[k]) { break; } node = node.children[k]; if (node.isEnd && f[j + 1]) { f[i] = true; break; } } } return f[0]; } class Trie { children: Trie[]; isEnd: boolean; constructor() { this.children = new Array(26); this.isEnd = false; } insert(w: string): void { let node: Trie = this; for (const c of w) { const i = c.charCodeAt(0) - 97; if (!node.children[i]) { node.children[i] = new Trie(); } node = node.children[i]; } node.isEnd = true; } }(code-box)

public class Solution { public bool WordBreak(string s, IList<string> wordDict) { Trie trie = new Trie(); foreach (string w in wordDict) { trie.Insert(w); } int n = s.Length; bool[] f = new bool[n + 1]; f[n] = true; for (int i = n - 1; i >= 0; --i) { Trie node = trie; for (int j = i; j < n; ++j) { int k = s[j] - 'a'; if (node.Children[k] == null) { break; } node = node.Children[k]; if (node.IsEnd && f[j + 1]) { f[i] = true; break; } } } return f[0]; } } class Trie { public Trie[] Children { get; set; } public bool IsEnd { get; set; } public Trie() { Children = new Trie[26]; IsEnd = false; } public void Insert(string word) { Trie node = this; foreach (char c in word) { int i = c - 'a'; if (node.Children[i] == null) { node.Children[i] = new Trie(); } node = node.Children[i]; } node.IsEnd = true; } }(code-box)