Solution For Word Break

Problem Statement:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

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

Solution:

Approach:

• We need to use dynamic programming to solve this problem.
• We will create a boolean array dp[] of size n+1, where n is the length of the given string s.
• Initially, all the elements of the dp[] array will be false.
• dp[i] will be true if the substring s[0, i) can be segmented into words present in the dictionary.
• To fill the dp[] array, we will iterate the string s from the left and for each substring s[0, i) check if there is any j (where 0 <= j < i) such that dp[j] is true and s[j, i) is present in the dictionary.

Step by Step solution:

• Initialize a hashset to store all the words in the dictionary so that lookups can be done efficiently.
• Initialize a boolean array dp of size n+1, where n is the length of the input string s.
• Fill the first element of the dp array with true, as an empty string can always be segmented.
• Iterate the string s from the first index to the last index.
• For each substring s[0, i), iterate from 0 to i.
• If dp[j] is true and s[j, i) is present in the dictionary, then mark dp[i] as true.
• Finally, return the value of dp[n], where n is the length of the input string s.

Time Complexity:

• The time complexity of this solution is O(n^2), where n is the length of the input string.
• We are iterating over the string twice, once to fill the boolean array dp and once to check for each substring if there is a split point or not.
• Lookup in the hashset is constant time, so it does not contribute to the time complexity.

Space Complexity:

• The space complexity of this solution is O(n), where n is the length of the input string.
• We are using a boolean array dp of size n+1.

Code:

Here’s the Python implementation of the above approach.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
words = set(wordDict)
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 words:
dp[i] = True
break

return dp[n]
``````

Step by Step Implementation For Word Break

`public boolean wordBreak(String s, List wordDict) { // edge case if (s == null || s.length() == 0) return false; // create a set for efficient lookup Set set = new HashSet<>(wordDict); // create an array to store results boolean[] dp = new boolean[s.length() + 1]; // base case dp[0] = true; // iterate through the string for (int i = 1; i <= s.length(); i++) { // iterate from the beginning of the string up to the current index for (int j = 0; j < i; j++) { // check if the string up to the current index can be broken up and if the current // substring is in the dictionary if (dp[j] && set.contains(s.substring(j, i))) { // if so, update the result at the current index dp[i] = true; // and break out of the inner loop break; } } } // return the result at the end of the string return dp[s.length()]; }`
```"""
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
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
"""

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
# Base case
if len(s) == 0:
return True

# Another base case
if len(wordDict) == 0:
return False

# Creating a set for faster lookup
wordDict = set(wordDict)

# Creating a memoization array
# -1 indicates that we have not processed that index yet
# 1 indicates that the string can be segmented from that index
# 0 indicates that the string cannot be segmented from that index
memo = [-1 for i in range(len(s))]

# Iterating through the string
for i in range(len(s)):

# If we have already processed this index, then we can just look up the result
if memo[i] != -1:
continue

# Otherwise, we need to process this index

# If the string starts with a word in the dictionary, then we can recurse
if s[:i+1] in wordDict:

# If the rest of the string can also be segmented, then we can return True
if self.wordBreak(s[i+1:], wordDict):
memo[i] = 1
continue

# If we get here, it means that the string cannot be segmented from this index
memo[i] = 0

# If we can segment the string from the last index, then we return True
# Otherwise, we return False
return memo[-1] == 1```
```var wordBreak = function(s, wordDict) {
// create a set for efficient lookup of words
const wordSet = new Set(wordDict);
// create a map to store results of previous calculations
// to avoid recalculating subproblems
const memo = {};

// define our recursive function
const canBreak = (startIndex) => {
// if we've already calculated this subproblem,
// return the stored result
if (memo.hasOwnProperty(startIndex)) {
return memo[startIndex];
}

// if we've reached the end of the string,
// we can return true
if (startIndex === s.length) {
return true;
}

// iterate through the string starting at the
// current index
for (let i = startIndex; i < s.length; i++) {
// if the current substring is in the word set,
// we can recurse with the remaining substring
// and OR the result with our current result
// to see if we can find a valid word break
// (ie, either the current substring is a word
// OR we can find a word after it)
if (wordSet.has(s.substring(startIndex, i + 1))) {
if (canBreak(i + 1)) {
// store the result and return
return memo[startIndex] = true;
}
}
}

// if we reach here, it means that we couldn't find
// a valid word break, so we return false
return memo[startIndex] = false;
};

// start the recursive call from the beginning
// of the string
return canBreak(0);
};```
```Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
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```
```public bool WordBreak(string s, IList wordDict) {

//create a hashset for efficient lookup
HashSet dict = new HashSet(wordDict);

//create an array to store whether a substring can be broken
bool[] canBreak = new bool[s.Length + 1];

//base case: empty string can always be broken
canBreak[0] = true;

//iterate through each substring
for(int i = 1; i <= s.Length; i++) {
//iterate through each possible breaking point
for(int j = 0; j < i; j++) {
//check if the substring up to the breaking point can be broken AND
//the substring from the breaking point to the end is in the dictionary
if(canBreak[j] && dict.Contains(s.Substring(j, i - j))) {
//if so, then the entire substring can be broken
canBreak[i] = true;

//no need to keep checking
break;
}
}
}

//return whether the entire string can be broken
return canBreak[s.Length];
}```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]