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]; 
}