String Segmentation

editor-page-cover

Problem Statement

You are given a dictionary of words and a large input string. You have to find out whether the input string can be completely segmented into the words of a given dictionary. The following two examples elaborate on the problem further.

widget

Hint

  • Memoization

Try it yourself

def can_segment_string(s, dictionary):
#TODO: Write - Your - Code
return False

Solution

def can_segment_string(s, dictionary) -> bool:
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # Empty string can be segmented
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in dictionary:
dp[i] = True
break
return dp[n]
s = "hellonow";
dictionary= set(["hello","hell","on","now"])
if can_segment_string(s, dictionary):
print("String Can be Segmented")
else:
print("String Can NOT be Segmented")

Solution Explanation

Runtime Complexity

The runtime complexity of this solution is exponential, O(2n)O(2^{n}).

Memory Complexity

The memory complexity of this solution is polynomial, O(n2)O(n^{2}).


Solution Breakdown

The algorithm iteratively checks substrings of the input string against the dictionary. Starting with an empty string being segmentable, it gradually builds up segmentability information for larger substrings by considering all possible substrings and checking if they exist in the dictionary. Once we determine that a substring can be segmented into words from the dictionary, we mark the corresponding entry in an array dp array as TRUE. Subsequently, when processing longer substrings, we use dp to check whether shorter substrings within them have already been determined to be segmentable, avoiding recomputations.

  1. Initialize a variable n with the length of the input word and create a boolean array dp with a size of n + 1. Initialize all values of dp to FALSE.
  2. Set dp[0] to TRUE to indicate that the empty string can be segmented.
  3. Iterate over the indexes of the word from 1 to n.
  4. For each index i, iterate over the indexes j from 0 to i - 1.
    • Check if dp[j] is TRUE and if the substring word[j:i] exists in the dictionary.
    • If both conditions are met, set dp[i] to TRUE.
  5. After completing the iterations, return dp[n] to indicate whether the entire word can be segmented.

Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!