# time complexity of word break algorithm

I found this question here but I don't think the answer is correct.

Here is the original word break question:

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

One way to do it is to use backtracking:

vector<string> wordBreak(string s, vector<string>& wordDict) {
vector<string> sentences;
string prefix = "";
findWords(prefix, 0, s, wordDict, sentences);
return sentences;
}

void findWords(string prefix, int start, const string s, const vector<string> &wordDict, vector<string> &sentences) {
if (start == s.size()) {
sentences.push_back(prefix);
return;
}
for (int i = start; i < s.size(); i++) {
string word = s.substr(start, i - start + 1);
if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
string new_prefix = prefix == "" ? word : prefix + " " + word;
findWords(new_prefix, i + 1, s, wordDict, sentences);
}
}
}


In the worst case, the dictionary contains all prefix of s. From my understanding, in this case, the time complexity is

T(n) = T(n-1) + T(n-2) + ... + T(1) = 2T(n-1) = O(2^n)


I'm not sure if this is correct because I see some threads say it is O(n^n)?

The other way is to use backtracking with memorization:

vector<string> wordBreak(string s, vector<string>& wordDict) {
return constructSentences(0, s, wordDict);
}

// Return all sentences that can be constructed using substring s[start, ...]
vector<string> constructSentences(int start, const string s, const vector<string> &wordDict) {
if (dict.count(start)) {
return dict[start];
}
vector<string> sentences;
if (start == s.size()) {
sentences.push_back("");
return sentences;
}
for (int i = start; i < s.size(); i++) {
string word = s.substr(start, i - start + 1);
if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
vector<string> subsentences = constructSentences(i + 1, s, wordDict);
dict[i + 1] = subsentences;
for (const auto elem : subsentences) {
sentences.push_back(elem == "" ? word : word + " " + elem);
}
}
}
return sentences;
}


I'm not sure how to analyze the time complexity of this approach since some subproblem can be solved in constant time by dictionary lookup but some cannot.

Furthermore, I'm not sure how to analyze the space complexity of these two approaches. From my understanding, the space is bounded by the final output. Since we have O(2^n) final sentence and each sentence have size O(n), does it mean the space complexity for both approach is O(2^n * n) ?

• You ask four questions at once; please focus on one for now. You may also want to check out our reference questions. Jun 1, 2017 at 4:36

## 1 Answer

If there is one string x that can be parsed in two ways then repeating x n times can be parsed in at least $2^n$ ways. So the problem has either 0, 1, or an exponential number of solutions. Asking for all is likely pointless.

However, you could provide an answer with many solutions in a much more compact format. Say your input is "catsanddog" repeated 100 times with $2^{100}$ solution, clearly infeasible. Instead we present a solution like this: "word1 word2 word3" if a solution consists of these three words. [solution1 | solution2 | solution3] if there are say three alternatives. And everything concatenated. So the solution in the case above would be written as ["cats and dog" | "cat sand dog"] repeated 100 times.

In practice, this will usually give a solution with size cN for a not very large c, where N is the input size. You can still have extremes. Take the dictionary ["a", "aa"] and a string of n a's as input. The first few solutions are:

"a": "a"
"aa": ["a a" | "aa"]
"aaa": ["a aa" | ["a a" | "aa"] "a"]
"aaaa": [["a a" | "aa"] "aa" | ["a aa" | ["a a" | "aa"] "a"] "a"]