Breaking of a sentence

Question

(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){
        results.add(path.toString());
    }
    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(), "");
            }
        }
    }
}

Answer 1

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, List<String> results) {
    if(givenSentence.length() == 0) {
        return;
    }

    if(dictionary.contains(givenSentence)) {
        results.add(path.toString() + 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(), "");
        }
    }
}

Answer 2

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.