(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, givens = 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 explainSpace 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(), );            }        }    }}
Breaking of a sentence
java;algorithm;interview questions
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(), );        }    }}