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&lt;String&gt; wordBreak(String s, Set&lt;String&gt; dict) {
    ArrayList&lt;String&gt; sentences = new ArrayList&lt;String&gt;();
    wordBreakHelper(s, dict, 0, new StringBuilder(), sentences);
    return sentences;
}
private static void wordBreakHelper(String givenSentence, Set&lt;String&gt; dictionary, int index, StringBuilder path, ArrayList&lt;String&gt; results){
    if(givenSentence.length() == 0){
        results.add(path.toString());
    }
    if(index &gt; givenSentence.length()){
        return;
    }
    for(int i = index; i &lt; 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&lt;String&gt; dictionary, StringBuilder path, List&lt;String&gt; results) {
    if(givenSentence.length() == 0) {
        return;
    }

    if(dictionary.contains(givenSentence)) {
        results.add(path.toString() + givenSentence);
    }

    for(int i = 1; i &lt; 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(), "");
        }
    }
}