# Breaking of a sentence

(Method signature is given with parameters)

Try to visualize me writing this code at an interview, and please be brutal while judging it.

Problem:

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"]

Time complexity: I don't know how to analyze it, $O(n)$, since I visit each char of the string for sure, but since I am backtracking, I visit it again constant time. I don't know, so please explain

Space Complexity: $O(n)$

public ArrayList<String> wordBreak(String s, Set<String> dict) {
ArrayList<String> sentences = new ArrayList<String>();
wordBreakHelper(s, dict, 0, new StringBuilder(), sentences);
return sentences;
}
private static void wordBreakHelper(String givenSentence, Set<String> dictionary, int index, StringBuilder path, ArrayList<String> results){
if(givenSentence.length() == 0){
}
if(index > givenSentence.length()){
return;
}
for(int i = index; i < givenSentence.length(); i++){
boolean isSpace = false;
if(dictionary.contains(givenSentence.substring(0, i+1))){
if(i+1 == givenSentence.length()){
path.append(givenSentence.substring(0, i+1));
}else{
path.append(givenSentence.substring(0, i+1) +" ");
isSpace = true;
}
wordBreakHelper(givenSentence.substring(i+1), dictionary, 0, path, results);
if(isSpace == true){
path.replace(path.length() - givenSentence.substring(0, i+2).length() , path.length(), "");
}else{
path.replace(path.length() - givenSentence.substring(0, i+1).length() , path.length(), "");
}
}
}
}
-

For the time and space complexity, think about how many sentences are possible with:

s = "aaaaaaaaaaa..."
dict = ["a", "aa"]

Any solutation that creates all of these sentences would need to have exponential complexity.

path.append(givenSentence.substring(0, i + 1) + " ");

If you are using a StringBuilder, you should use its append method instead of the '+' operator as it's more efficient.

The index parameter is always 0. This can be removed.

givenSentence.substring(0, i + 1) is used multiple times. You can assign this to a variable and reuse it instead.

if(isSpace == true)

There's no need to compare with true. Just use if(isSpace)

givenSentence.substring(0, i + 2).length()

Calling substring just to get the length of the String is unnessesary. This is the same as i + 2.

The handling of isSpace adds some complexity. There is some code duplication and extra if statements needed. I would try to remove the need for this.

Changing the bounds of the for-loop can remove the need for adding one to i each time it's used.

With these changes, you have something like:

private static void wordBreakHelper(String givenSentence, Set<String> dictionary, StringBuilder path, ArrayList<String> results) {
if(givenSentence.length() == 0) {
return;
}

if(dictionary.contains(givenSentence)) {
}

for(int i = 1; i < givenSentence.length(); i++) {
String nextWord = givenSentence.substring(0, i);
if(dictionary.contains(nextWord)) {
path.append(nextWord).append(" ");
wordBreakHelper(givenSentence.substring(i), dictionary, path, results);
path.replace(path.length() - nextWord.length() - 1, path.length(), "");
}
}
}
-
can you explain the worst case complexity of the code in broader detail; I can see how it is expnonential but have a hard time grasping an upper bound on it –  bazang Apr 26 '14 at 23:45
@bazang If there are w words in dict, and n letters in s: a sentence can contain at most n words. There's w possibilities for each word: So at most O(w^n) sentences. Each sentence will require at least O(n^2) time because the calls to substring for each word (substring is O(n), can be called n times for each sentence). The calls to append and replace aren't any more than that. I'm not sure if the loop adds anything here or if it's already accounted for. That adds up to O(w^n * n^2) time, O(w^n * n) space. –  fgb Apr 27 '14 at 0:23

I don't believe you program is $O(n)$ because you recursively call wordBreakHelper in a loop, which I believe actually makes this an exponential time algorithm. This is because your $O(n)$ loop potentially run $O(n)$ times ($O(n^n)$).

Two quick comments on the code, though:

• Be consistent in your parameter names. For example, you have both dict and dictionary.

• There's no reason to require ArrayList parameter types over simple List types.

-
The method signature was provided in the problem. –  bazang Apr 26 '14 at 22:15
That doesn't necessarily mean you have to keep it, as any calling code wouldn't be affected. It's a trivial point though, and you demonstrate the use of descriptive variable names in the wordBreakHelper signature. –  lealand Apr 26 '14 at 22:22