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.

- Memoization

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

def can_segment_string(s, dictionary) -> bool:n = len(s)dp = [False] * (n + 1)dp[0] = True # Empty string can be segmentedfor i in range(1, n + 1):for j in range(i):if dp[j] and s[j:i] in dictionary:dp[i] = Truebreakreturn 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")

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

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

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.

- 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. - Set
`dp[0]`

to TRUE to indicate that the empty string can be segmented. - Iterate over the indexes of the word from 1 to
`n`

. - 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.

- Check if
- 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!

TRENDING TOPICS