Jobs

Interviews

Discussions

Word Break II

Hard

Amazon

3 views

Topics:

StringsDynamic ProgrammingRecursion

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

For example:

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Write a function to solve this problem efficiently. Consider the time and space complexity of your solution. Also, discuss edge cases like an empty input string or a dictionary that doesn't allow for any valid sentence.

Word Break II

Hard

Amazon

3 views

Topics:

StringsDynamic ProgrammingRecursion

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

For example:

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the same word in the dictionary be used multiple times in the same segmentation?
What should I return if the string `s` cannot be segmented using the words in `wordDict`?
Are there any constraints on the length of the input string `s` and the words in `wordDict`? Are there any memory constraints I should consider?
Is the `wordDict` case-sensitive? Should I assume the input string `s` is also case-sensitive?
Is the order of the segmentations in the returned list important?

Brute Force Solution

Approach

The brute force approach attempts to find all possible ways to break a large piece of text into a sequence of valid words. We explore every single potential combination of word breaks. The main idea is to exhaustively try every possible split and check if the resulting sequence is made up of valid words from the given dictionary.

Here's how the algorithm would work step-by-step:

Consider all possible starting points for the first word in your sentence.
For each starting point, check if the segment of the input string beginning there is a valid word.
If it is a valid word, remember this first word choice and move on to the remaining part of the sentence.
Repeat this process for the remaining part of the sentence: find all possible valid word segments and keep track of those choices.
Continue breaking down the sentence into potential valid words until you have either successfully used all of the original sentence or you are unable to make any further valid word segmentations.
If at any point you can't form any further valid words, backtrack to a previous choice point and explore different segmentation options.
If you successfully segmented the whole original sentence into valid words, record the resulting sequence of words as a possible solution.
Repeat the entire process to identify every single possible valid sentence composed of words from the dictionary. You will end up with all the valid sentences.

Code Implementation

def word_break_brute_force(text, word_dictionary):
    result_sentences = []
    
    def backtrack(current_sentence, remaining_text):
        # If no text remaining, the sentence is valid
        if not remaining_text:
            result_sentences.append(" ".join(current_sentence))
            return

        for index in range(1, len(remaining_text) + 1):
            potential_word = remaining_text[:index]
            
            # Check if the segment is a valid word
            if potential_word in word_dictionary:
                # Add to current sentence and recurse
                backtrack(current_sentence + [potential_word], remaining_text[index:])

    backtrack([], text)
    return result_sentences

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores every possible segmentation of the input string of length n. In the worst case, we might consider cutting the string at every possible position, leading to 2^(n-1) possible segmentations. For each segmentation, we need to verify if the resulting words are in the dictionary, taking additional time, but the dominant factor is the exponential number of possible splits. Therefore, the time complexity is O(2^n) reflecting this exponential growth in the number of explored sentence structures.

Space Complexity

O(N^2) – The described brute force approach uses recursion. The maximum depth of the recursion can be N, where N is the length of the input string, as we potentially make a recursive call for each position in the string. At each level of the recursion, we are potentially storing a substring of the input string and a list of words that form the sentence so far, and the size of the substring can be at most N, leading to potential storage of N length substrings at each recursive call and hence N*N space complexity. Furthermore, in the worst case, the number of valid sentences could be exponential, but the length of each sentence is still bound by N. The space used by the list to store the possible sentences also adds up, however the length of each sentence is bounded by N which is already captured in O(N^2).

Optimal Solution

Approach

The core idea is to break down the problem into smaller, overlapping subproblems. We use a memory technique to avoid recalculating results we've already found, making the solution much faster. This allows us to explore the possibilities efficiently, remembering previous good choices.

Here's how the algorithm would work step-by-step:

First, check if it's even possible to make the entire string using the words in the given dictionary. If it isn't, we can stop right away and say no solution exists.
Start from the beginning of the string. For each possible breaking point, check if the substring up to that point can be made using words from the dictionary.
If a substring can be made, store the different ways to make it. This is our memory, so we don't have to figure it out again later.
Now, for each stored way to make a substring, look at the remaining part of the string. Try to break it down further using words from the dictionary.
Keep doing this until you reach the end of the string. If you can reach the end, you've found a valid sentence. Add this sentence to your list of results.
Since we stored all the ways to make each substring, we can find all possible sentences by combining them in different ways. This gives us every valid solution without redoing work.

Code Implementation

def word_break(input_string, word_dictionary):    def is_breakable(string_to_check, word_set):        breakable = [False] * (len(string_to_check) + 1)
        breakable[0] = True
        for i in range(1, len(string_to_check) + 1):
            for j in range(i):
                if breakable[j] and string_to_check[j:i] in word_set:
                    breakable[i] = True
                    break
        return breakable[-1]

    if not is_breakable(input_string, set(word_dictionary)):        return []    memo = {}

    def word_break_helper(remaining_string, word_set):        if not remaining_string:
            return [""]

        if remaining_string in memo:
            return memo[remaining_string]

        sentences = []
        for word in word_set:
            if remaining_string.startswith(word):
                suffix = remaining_string[len(word):]
                suffix_sentences = word_break_helper(suffix, word_set)
                for sentence in suffix_sentences:
                    sentences.append(word + (" " + sentence if sentence else ""))

        memo[remaining_string] = sentences
        return sentences    # Use a helper function with memoization.    result = word_break_helper(input_string, set(word_dictionary))

    # Return the sentences constructed.    return result

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm uses dynamic programming with memoization to explore all possible ways to break the string. In the worst-case scenario, where the dictionary contains many short words, there could be an exponential number of ways to segment the string. Specifically, consider a string 'aaaa' and a dictionary {'a', 'aa', 'aaa', 'aaaa'}. Each position can be a break point, leading to exponential possibilities. Therefore, the time complexity in the worst case is O(2^n), where n is the length of the input string.

Space Complexity

O(N^2) – The algorithm uses memoization to store the possible ways to construct substrings. In the worst case, we might store results for all possible substrings of the input string, which can be N(N+1)/2, where N is the length of the string. This occurs when every prefix of the string can be segmented into words from the dictionary. Consequently, the space required for memoization scales quadratically with the input size. Therefore, auxiliary space complexity is O(N^2).

Edge Cases

Case	How to Handle
Empty input string s	Return an empty list if the input string is empty, as there are no segmentations possible.
Null input string s or null wordDict	Throw an IllegalArgumentException or return an empty list to handle null inputs gracefully.
Empty wordDict	Return an empty list if the dictionary is empty, as no words can be formed.
No valid segmentation possible	Return an empty list when the input string cannot be segmented using the given dictionary.
WordDict contains an empty string	Handle carefully to avoid infinite recursion or incorrect segmentations; typically it is excluded from being added into the data structure.
Very long input string s (scalability)	Memoization/dynamic programming is essential for performance with long strings to avoid exponential time complexity.
WordDict contains very long words	Consider the memory and time cost of checking very long words against substrings; prefiltering based on length may improve performance.
Input string s is a very long repetition of a single character	Ensure the solution handles this gracefully, avoiding stack overflow with deep recursion by using memoization or dynamic programming.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the same word in the dictionary be used multiple times in the same segmentation?
What should I return if the string `s` cannot be segmented using the words in `wordDict`?
Are there any constraints on the length of the input string `s` and the words in `wordDict`? Are there any memory constraints I should consider?
Is the `wordDict` case-sensitive? Should I assume the input string `s` is also case-sensitive?
Is the order of the segmentations in the returned list important?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Consider all possible starting points for the first word in your sentence.
For each starting point, check if the segment of the input string beginning there is a valid word.
If it is a valid word, remember this first word choice and move on to the remaining part of the sentence.
Repeat this process for the remaining part of the sentence: find all possible valid word segments and keep track of those choices.
Continue breaking down the sentence into potential valid words until you have either successfully used all of the original sentence or you are unable to make any further valid word segmentations.
If at any point you can't form any further valid words, backtrack to a previous choice point and explore different segmentation options.
If you successfully segmented the whole original sentence into valid words, record the resulting sequence of words as a possible solution.
Repeat the entire process to identify every single possible valid sentence composed of words from the dictionary. You will end up with all the valid sentences.

Code Implementation

def word_break_brute_force(text, word_dictionary):
    result_sentences = []
    
    def backtrack(current_sentence, remaining_text):
        # If no text remaining, the sentence is valid
        if not remaining_text:
            result_sentences.append(" ".join(current_sentence))
            return

        for index in range(1, len(remaining_text) + 1):
            potential_word = remaining_text[:index]
            
            # Check if the segment is a valid word
            if potential_word in word_dictionary:
                # Add to current sentence and recurse
                backtrack(current_sentence + [potential_word], remaining_text[index:])

    backtrack([], text)
    return result_sentences

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if it's even possible to make the entire string using the words in the given dictionary. If it isn't, we can stop right away and say no solution exists.
Start from the beginning of the string. For each possible breaking point, check if the substring up to that point can be made using words from the dictionary.
If a substring can be made, store the different ways to make it. This is our memory, so we don't have to figure it out again later.
Now, for each stored way to make a substring, look at the remaining part of the string. Try to break it down further using words from the dictionary.
Keep doing this until you reach the end of the string. If you can reach the end, you've found a valid sentence. Add this sentence to your list of results.
Since we stored all the ways to make each substring, we can find all possible sentences by combining them in different ways. This gives us every valid solution without redoing work.

Code Implementation

def word_break(input_string, word_dictionary):    def is_breakable(string_to_check, word_set):        breakable = [False] * (len(string_to_check) + 1)
        breakable[0] = True
        for i in range(1, len(string_to_check) + 1):
            for j in range(i):
                if breakable[j] and string_to_check[j:i] in word_set:
                    breakable[i] = True
                    break
        return breakable[-1]

    if not is_breakable(input_string, set(word_dictionary)):        return []    memo = {}

    def word_break_helper(remaining_string, word_set):        if not remaining_string:
            return [""]

        if remaining_string in memo:
            return memo[remaining_string]

        sentences = []
        for word in word_set:
            if remaining_string.startswith(word):
                suffix = remaining_string[len(word):]
                suffix_sentences = word_break_helper(suffix, word_set)
                for sentence in suffix_sentences:
                    sentences.append(word + (" " + sentence if sentence else ""))

        memo[remaining_string] = sentences
        return sentences    # Use a helper function with memoization.    result = word_break_helper(input_string, set(word_dictionary))

    # Return the sentences constructed.    return result

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input string s	Return an empty list if the input string is empty, as there are no segmentations possible.
Null input string s or null wordDict	Throw an IllegalArgumentException or return an empty list to handle null inputs gracefully.
Empty wordDict	Return an empty list if the dictionary is empty, as no words can be formed.
No valid segmentation possible	Return an empty list when the input string cannot be segmented using the given dictionary.
WordDict contains an empty string	Handle carefully to avoid infinite recursion or incorrect segmentations; typically it is excluded from being added into the data structure.
Very long input string s (scalability)	Memoization/dynamic programming is essential for performance with long strings to avoid exponential time complexity.
WordDict contains very long words	Consider the memory and time cost of checking very long words against substrings; prefiltering based on length may improve performance.
Input string s is a very long repetition of a single character	Ensure the solution handles this gracefully, avoiding stack overflow with deep recursion by using memoization or dynamic programming.