Given a dictionary of words and a string with all spaces removed, determine whether the string is composed of valid words

Problem Statement

Given a dictionary of words and a string with all spaces removed, determine whether the string is composed of valid words

Examples

helloworld-> hello world (valid)

isitniceinhere-> is it nice in here (valid)

zxyy-> invalid

Time Complexity Requirement

O(n^2)

Algorithm

True/False array T of size equal to the input. T[i] = true => the substring starting from i is composed of valid words.

Assume API method IsValidWord() is O(1) since we are given a dictionary.

for each element in the array:

T[i] = (IsValidWord(s.substring(i, 1)) && T[i+1])

|| (IsValidWord(s.substring(i, 2)) && T[i+2])

...

|| (IsValidWord(s.substring(i, n-i-1)) && T[n-1])

The result is T[0].

Complexity analysis

for each i, it takes O(n) to compute. and we start the computation from i = s.length - 1 and decrease i, and there are n element in the array to compute. So we get O(n^2) as the total time complexity.