Solution 1: Dynamic Programming

Here’s a Python implementation of the word_break function using dynamic programming:

from typing import List

def word_break(s: str, wordDict: List[str]) -> bool:
    # Create a set for faster word lookup
    word_set = set(wordDict)

    # Create an array to store whether the substring ending at index i can be segmented
    dp = [False] * (len(s) + 1)
    # Base case: an empty string can always be segmented
    dp[0] = True

    # Iterate through the string
    for i in range(1, len(s) + 1):
        # Check if the substring s[:i] can be segmented
        for j in range(i):
            # If the prefix s[:j] can be segmented and the substring s[j:i] is in the word dictionary
            # Update dp[i] to True
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    # Return whether the entire string s can be segmented
    return dp[len(s)]

# Example usage:
result = word_break("daynight", ["day", "night"])
print(result)  # Output: True

result = word_break("daynight", ["day", "noon", "nigh"])
print(result)  # Output: False

result = word_break("applepenapple", ["apple", "pen"])
print(result)  # Output: True

Explanation:

  • We use dynamic programming to solve this problem. The idea is to check if each prefix of the string s can be segmented into words from the dictionary.
  • We initialize a boolean list dp, where dp[i] represents whether the substring s[:i] can be segmented.
  • We iterate through each position i in the string and check if any prefix s[:j] (where 0 <= j < i) can be segmented and if the remaining substring s[j:i] is present in the word dictionary. If both conditions are true, we update dp[i] to True.
  • Finally, we return dp[len(s)], which represents whether the entire string s can be segmented.

Time Complexity:

  • The time complexity of this solution is O(n^2), where n is the length of the input string s. This is because we have nested loops, one iterating through each position in the string and the other iterating through each prefix of the string.

Space Complexity:

  • The space complexity is O(n), where n is the length of the input string s. This is because we use an additional boolean list dp of length n+1 to store whether each prefix of s can be segmented.

We can use Breadth-First Search (BFS) to solve the “Word Break” problem. Here’s how it can be implemented:

from typing import List
from collections import deque

def word_break(s: str, wordDict: List[str]) -> bool:
    # Create a set from the word dictionary for faster lookup
    word_set = set(wordDict)
    
    # Initialize a queue for BFS
    queue = deque([0])  # Start BFS from the beginning of the string
    
    # Initialize a set to store visited indices
    visited = set()
    
    # Iterate through the queue using BFS
    while queue:
        start = queue.popleft()
        
        # If the current start index is already visited, skip it
        if start in visited:
            continue
        
        # Mark the current start index as visited
        visited.add(start)
        
        # Iterate through all possible end positions for the current start index
        for end in range(start + 1, len(s) + 1):
            # Check if the substring s[start:end] is in the word dictionary
            if s[start:end] in word_set:
                # If the end index is at the end of the string, return True
                if end == len(s):
                    return True
                
                # Add the end index to the queue for further exploration
                queue.append(end)
    
    # If BFS completes without finding a valid segmentation, return False
    return False

# Example usage:
print(word_break("daynight", ["day", "night"]))  # Output: True
print(word_break("daynight", ["day", "noon", "nigh"]))  # Output: False
print(word_break("applepenapple", ["apple", "pen"]))  # Output: True

Explanation:

  • We use Breadth-First Search (BFS) to explore all possible segmentations of the input string s.
  • We start BFS from the beginning of the string and explore all possible end positions for each start index.
  • If we find a valid word, we add the corresponding end index to the BFS queue for further exploration.
  • We keep track of visited indices to avoid revisiting the same indices.

Time Complexity:

The time complexity of the Breadth-First Search (BFS) solution for the “Word Break” problem is O(n^2), where n is the length of the input string s.

Here’s the breakdown of the time complexity:

  1. Outer Loop Iterations:
    • The outer loop of the BFS algorithm iterates over each character in the input string s.
    • In the worst case, the outer loop iterates over all n characters of the string s.
  2. Inner Loop Iterations:
    • For each character in the input string s, the inner loop iterates over all possible substrings starting from that character.
    • In the worst case, the inner loop iterates over all n characters of the string s for each character in the input string.
    • Therefore, the total number of inner loop iterations is O(n^2).
  3. Substring Check:
    • For each possible substring, we perform a lookup in the word dictionary to check if it is a valid word.
    • The lookup operation in the word dictionary can be assumed to have constant time complexity, as it uses a set for efficient membership checking.
  4. Overall:
    • Combining the iterations of the outer and inner loops, and considering the constant-time complexity of the substring check, the overall time complexity of the BFS solution is O(n^2).

In summary, the BFS solution involves exploring all possible substrings of the input string s and checking if they form valid words. The time complexity is determined by the number of iterations of the outer and inner loops, leading to a quadratic time complexity of O(n^2) in the worst case.

Space Complexity:

  • The space complexity is O(n + m), where n is the length of the input string s and m is the number of words in the dictionary. This is because we use a queue of size O(n) for BFS and a word_set of size O(m). Additionally, we use a set to store visited indices, which can also have a maximum size of O(n).