# Word Break LeetCode Solution

Here, We see Word Break LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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

## Word Break LeetCode Solution C++

``````class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
const int n = s.length();
const int maxLength = getMaxLength(wordDict);
const unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
vector<int> dp(n + 1);
dp[0] = true;
for (int i = 1; i <= n; ++i)
for (int j = i - 1; j >= 0; --j) {
if (i - j > maxLength)
break;
if (dp[j] && wordSet.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}

return dp[n];
}

private:
int getMaxLength(const vector<string>& wordDict) {
return max_element(begin(wordDict), end(wordDict),
[](const auto& a, const auto& b) {
return a.length() < b.length();
})
->length();
}
};```Code language: PHP (php)```

## Word Break LeetCode Solution Java

``````class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
return recWay1(s, wordDict);
}

boolean recWay2(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak2(s, new HashSet<>(wordDict), 0, memo);
}
boolean wordBreak2(String s, Set<String> wordDict, int k, Boolean[] memo) {
int n = s.length();
if (k == n) return true;
if (memo[k] != null) return memo[k];
for (int i=k + 1; i<=n; i++) {
String word = s.substring(k, i);
if (wordDict.contains(word) && wordBreak2(s, wordDict, i, memo)) {
return memo[k] = true;
}
}
return memo[k] = false;
}
boolean recWay1(String s, List<String> wordDict) {
Boolean[] memo = new Boolean[s.length() + 1];
return wordBreak(s, wordDict, 0, memo);
}
boolean wordBreak(String s, List<String> wordDict, int k, Boolean[] memo) {
if (k == s.length()) {
return true;
}
if (memo[k] != null) {
return memo[k];
}
for (int i=0; i<wordDict.size(); i++) {
String word = wordDict.get(i);
if (s.startsWith(word, k)) {
if(wordBreak(s, wordDict, k + word.length(), memo)) return memo[k] = true;
}
}
return memo[k] = false;
}
}```Code language: JavaScript (javascript)```

## Word Break LeetCode Solution JavaScript

``````var wordBreak = function(s, wordDict) {
let n = s.length;
let dp = new Array(n + 1).fill(false);
dp[0] = true;
let max_len = Math.max(...wordDict.map(word => word.length));
for (let i = 1; i <= n; i++) {
for (let j = i - 1; j >= Math.max(i - max_len - 1, 0); j--) {
if (dp[j] && wordDict.includes(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
};```Code language: JavaScript (javascript)```

## Word Break LeetCode Solution Python

``````class Solution(object):
def wordBreak(self, s, wordDict):
def construct(current,wordDict, memo={}):
if current in memo:
return memo[current]
if not current:
return True
for word in wordDict:
if current.startswith(word):
new_current = current[len(word):]
if construct(new_current,wordDict,memo):
memo[current] = True
return True
memo[current] = False
return False
return construct(s,wordDict)``````
Scroll to Top