Word Break Ii

                                            
class Solution {
public:
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        unordered_map<string, vector<string>> memo;

        return wordBreakHelper(s, dict, memo);
    }
    
    vector<string> wordBreakHelper(string s, unordered_set<string>& dict, unordered_map<string, vector<string>>& memo) {
        if (memo.find(s) != memo.end()) {
            return memo[s];
        }
        
        vector<string> result;
        
        if (s.empty()) {
            result.push_back("");
            return result;
        }
        
        for (string word : dict) {
            if (s.substr(0, word.length()) == word) {
                vector<string> subList = wordBreakHelper(s.substr(word.length()), dict, memo);
                
                for (string sub : subList) {
                    result.push_back(word + (sub.empty() ? "" : " ") + sub);
                }
            }
        }
        
        memo[s] = result;
        return result;
    }
};

                                            
class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        backtrack(s, wordDict, result, new StringBuilder(), 0);
        return result;
    }
    
    private void backtrack(String s, List<String> wordDict, List<String> result, StringBuilder sb, int start) {
        if (start == s.length()) {
            result.add(sb.toString().trim());
            return;
        }
        
        for (String word : wordDict) {
            if (s.startsWith(word, start)) {
                int len = word.length();
                int sbLen = sb.length();
                sb.append(word).append(" ");
                backtrack(s, wordDict, result, sb, start + len);
                sb.setLength(sbLen);
            }
        }
    }
}

                                            
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        def backtrack(start, path):
            if start == len(s):
                result.append(' '.join(path))
                return
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in wordDict:
                    backtrack(end, path + [s[start:end]])
        
        result = []
        backtrack(0, [])
        return result

                                            
public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        var dict = new HashSet<string>(wordDict);
        return WordBreakHelper(s, dict, new Dictionary<string, List<string>>());
    }
    
    private IList<string> WordBreakHelper(string s, HashSet<string> dict, Dictionary<string, List<string>> memo) {
        if (memo.ContainsKey(s)) {
            return memo[s];
        }
        
        var result = new List<string>();
        
        if (dict.Contains(s)) {
            result.Add(s);
        }
        
        for (int i = 1; i < s.Length; i++) {
            string right = s.Substring(i);
            if (dict.Contains(right)) {
                IList<string> left = WordBreakHelper(s.Substring(0, i), dict, memo);
                foreach (string l in left) {
                    result.Add(l + " " + right);
                }
            }
        }
        
        memo[s] = result;
        return result;
    }
}

                                            
/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {string[]}
 */
var wordBreak = function(s, wordDict) {
    const wordSet = new Set(wordDict);
    const memo = new Map();
    
    const helper = (start) => {
        if (memo.has(start)) return memo.get(start);
        
        const results = [];
        if (start === s.length) {
            results.push('');
        }
        
        for (let end = start + 1; end <= s.length; end++) {
            const word = s.substring(start, end);
            if (wordSet.has(word)) {
                const suffixes = helper(end);
                for (const suffix of suffixes) {
                    results.push(word + (suffix === '' ? '' : ' ') + suffix);
                }
            }
        }
        
        memo.set(start, results);
        return results;
    };
    
    return helper(0);
};

                                            
function wordBreak(s: string, wordDict: string[]): string[] {
    const wordSet = new Set(wordDict);
    const memo: { [key: string]: string[]} = {};

    const backtrack = (startIndex: number): string[] => {
        if (memo[startIndex]) {
            return memo[startIndex];
        }

        if (startIndex === s.length) {
            return [""];
        }

        const result: string[] = [];

        for (let endIndex = startIndex + 1; endIndex <= s.length; endIndex++) {
            const word = s.substring(startIndex, endIndex);
            if (wordSet.has(word)) {
                const nextWords = backtrack(endIndex);
                for (const nextWord of nextWords) {
                    result.push(nextWord ? word + " " + nextWord : word);
                }
            }
        }

        memo[startIndex] = result;
        return result;
    };

    return backtrack(0);
};

                                            
class Solution {
    /**
     * @param String $s
     * @param String[] $wordDict
     * @return String[]
     */
    function wordBreak($s, $wordDict) {
        $memo = [];
        return $this->dfs($s, $wordDict, $memo);
    }
    
    function dfs($s, $wordDict, &$memo) {
        if (array_key_exists($s, $memo)) {
            return $memo[$s];
        }
        
        $result = [];
        foreach ($wordDict as $word) {
            if (strpos($s, $word) === 0) {
                $subStr = substr($s, strlen($word));
                if (strlen($subStr) == 0) {
                    $result[] = $word;
                } else {
                    $subResult = $this->dfs($subStr, $wordDict, $memo);
                    foreach ($subResult as $w) {
                        $result[] = $word . " " . $w;
                    }
                }
            }
        }
        
        $memo[$s] = $result;
        return $result;
    }
}

                                            
class Solution {
    func wordBreak(_ s: String, _ wordDict: [String]) -> [String] {
        var memo = [String: [String]]()

        func backtrack(_ s: String) -> [String] {
            if let result = memo[s] {
                return result
            }

            var sentences = [String]()

            for word in wordDict {
                if s.hasPrefix(word) {
                    let nextWordIndex = s.index(s.startIndex, offsetBy: word.count)
                    if nextWordIndex == s.endIndex {
                        sentences.append(word)
                    } else {
                        let nextSubstring = String(s[nextWordIndex...])
                        let nextSentences = backtrack(nextSubstring)
                        for nextSentence in nextSentences {
                            sentences.append(word + " " + nextSentence)
                        }
                    }
                }
            }

            memo[s] = sentences
            return sentences
        }

        return backtrack(s)
    }
}

                                            
class Solution {
    fun wordBreak(s: String, wordDict: List<String>): List<String> {
        val map = HashMap<String, List<String>>()

        fun wordBreakHelper(s: String): List<String> {
            if (map.containsKey(s)) {
                return map[s]!!
            }

            val result = mutableListOf<String>()

            if (s.isEmpty()) {
                result.add("")
                return result
            }

            for (word in wordDict) {
                if (s.startsWith(word)) {
                    val subList = wordBreakHelper(s.substring(word.length))
                    for (sub in subList) {
                        result.add(if (sub.isEmpty()) word else "$word $sub")
                    }
                }
            }

            map[s] = result
            return result
        }

        return wordBreakHelper(s)
    }
}

                                            
class Solution {
  List<String> wordBreak(String s, List<String> wordDict) {
    List<String> result = [];
    if (s.isEmpty) {
      return result;
    }
    return wordBreakHelper(s, wordDict, {});
  }

  List<String> wordBreakHelper(String s, List<String> wordDict, Map<String, List<String>> memo) {
    if (memo.containsKey(s)) {
      return memo[s]!;
    }
    List<String> result = [];
    if (s.isEmpty) {
      result.add("");
      return result;
    }
    for (String word in wordDict) {
      if (s.startsWith(word)) {
        List<String> subList = wordBreakHelper(s.substring(word.length), wordDict, memo);
        for (String sub in subList) {
          result.add(word + (sub.isEmpty ? "" : " ") + sub);
        }
      }
    }
    memo[s] = result;
    return result;
  }
}

                                            
# @param {String} s
# @param {String[]} word_dict
# @return {String[]}
def word_break(s, word_dict)
    result = []
    backtrack(s, word_dict, "", result)
    return result
end

def backtrack(s, word_dict, path, result)
    if s == ""
        result << path.strip
        return
    end
    
    word_dict.each do |word|
        if s.start_with?(word)
            backtrack(s[word.length..-1], word_dict, "#{path} #{word}", result)
        end
    end
end

                                            
object Solution {
    def wordBreak(s: String, wordDict: List[String]): List[String] = {
        import scala.collection.mutable.Map

        var map = Map[String, List[String]]()

        def wordBreakHelper(s: String): List[String] = {
            if (map.contains(s)) return map(s)

            var res = List[String]()
            if (s.isEmpty) {
                res = List("")
            } else {
                for (word <- wordDict) {
                    if (s.startsWith(word)) {
                        val subList = wordBreakHelper(s.substring(word.length))
                        for (sub <- subList) {
                            res = (if (sub.isEmpty) word else word + " " + sub) :: res
                        }
                    }
                }
            }
            map += (s -> res)
            res
        }

        wordBreakHelper(s)
    }
}

                                            
impl Solution {
    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
        use std::collections::{HashMap, HashSet};

        fn backtrack(
            s: &str,
            word_dict: &HashSet<String>,
            memo: &mut HashMap<String, Vec<String>>,
        ) -> Vec<String> {
            if let Some(result) = memo.get(s) {
                return result.clone();
            }

            let mut sentences = vec![];
            if word_dict.contains(s) {
                sentences.push(s.to_string());
            }

            for i in 1..s.len() {
                let (word_left, word_right) = s.split_at(i);
                if word_dict.contains(word_left) {
                    let previous_sentences = backtrack(word_right, word_dict, memo);
                    for sentence in previous_sentences {
                        let space = if !sentence.is_empty() { " " } else { "" };
                        sentences.push(format!("{}{}{}", word_left, space, sentence));
                    }
                }
            }

            memo.insert(s.to_string(), sentences.clone());
            sentences
        }

        let word_dict_set: HashSet<String> = word_dict.iter().cloned().collect();
        let result = backtrack(&s, &word_dict_set, &mut HashMap::new());

        result
    }
}

To solve this coding challenge, we need to break down the problem statement and develop an understanding of how to approach it using a combination of recursive backtracking and dynamic programming.

Explanation

The problem asks us to determine all possible ways to break a given string

s

into valid words found in the dictionary

wordDict

. To do this effectively, we need to explore all possible ways to insert spaces in the string

s

such that each segmented part is a valid word from the dictionary. A viable approach to solve this challenge would be using backtracking along with memoization to keep track of already explored segments to optimize and avoid redundant computations.

Steps to Approach the Problem:

Backtracking : We need to use backtracking to explore all possible breaks in the string
s

.
Memoization : To optimize the solution, use a dictionary to memoize results for already computed substrings. This will help avoid recomputation and improve performance significantly.
Recursive Subroutine : Define a recursive subroutine that attempts to break the string from the current position to the end. If a valid word is found in the dictionary, recursively call the subroutine for the next segment.
Base Case : The base case occurs when the starting index reaches the end of the string
s

. At this point, the constructed path will represent one of the possible valid sentences.

Here’s how the pseudocode would look, incorporating detailed comments to explain each step:

                                            
# Function to perform the word break operation
FUNCTION wordBreak(s: STRING, wordDict: LIST OF STRINGS) -> LIST OF STRINGS
# Convert wordDict list to a set for O(1) look-up times
wordSet <- CONVERT_TO_SET(wordDict)

# Dictionary to memoize results for different starting indices
memo <- EMPTY_MAP

# Internal helper function for backtracking
FUNCTION backtrack(start: INTEGER) -> LIST OF STRINGS
# Check if the current start index is already memoized
IF start IN memo THEN
RETURN memo[start]

# Initialize a list to store sentences created from the current start index
sentences <- EMPTY_LIST

# Base Case: If we have reached the end of the string, return an empty path
IF start == LENGTH(s) THEN
sentences.APPEND("")
RETURN sentences

# Iterate over all possible end indices to create substrings from start to end
FOR end FROM start + 1 TO LENGTH(s) + 1 DO
currentSubstring <- SUBSTRING(s, start, end)

# Check if the current substring is a valid word
IF currentSubstring IN wordSet THEN
# Recursively call backtrack for the remaining part of the string
CONTINUE_SENTENCES <- backtrack(end)

# Concatenate the current word with the results from recursive call
FOR sentence IN CONTINUE_SENTENCES DO
IF sentence == "" THEN
sentences.APPEND(currentSubstring)
ELSE
sentences.APPEND(currentSubstring + " " + sentence)

# Memoize the results for the current start index
memo[start] <- sentences
RETURN sentences

# Initiate the backtracking from the start of the string
RETURN backtrack(0)

Step-by-Step Explanation

Initialization :

Convert
wordDict

to a set called
wordSet

for faster lookup.
Define a memoization dictionary
memo

to store results of subproblems.

Backtracking Function :

Create an internal function
backtrack

that will recursively try to break the string.
If the result for the current
start

is already in
memo

, return the memoized result.

Base Case :

If
start

equals the length of
s

, append an empty string to the list
sentences

to signify a valid segmentation and return it.

Iterate Over Possible Breaks :

Loop through possible end indices and extract the current substring.
If the substring is a valid word in
wordSet

, perform a recursive call to
backtrack

from the current
end

index.

Concatenate Results :

For each result from the recursive call, concatenate the current substring with the sentences generated from the subsequent recursive breaks.
Handle the case where the sentence is empty separately to avoid leading spaces.

Memoization and Return :

Store the generated sentences in
memo

to use in future calls.
Start the backtracking process from the beginning of the string and return the result.

By following this detailed step-by-step explanation and pseudocode, you can efficiently solve the problem of finding all valid word breaks for the given string using the provided dictionary.