Step 1 : Was able to recognize that it was a question of backtracking.
Step 2 : Created a unordered hashmap to check if any string is part of dictionary or not.
Step 3 : Traverse the string in recursive...read more

We need to keep exploring the given string from current position ‘i’ to until we wouldn’t find a position such that substring ‘i’ to ‘j’ exists in the dictionary.

Algorithm:

• Store all words of...read more

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems m...read more

The idea is to use Trie data structure. 

A trie is a tree-like data structure whose nodes store the letters of an alphabet. By structuring the nodes in a particular way, words and strings can be retrieved from the structure by traversing down a branch path of the tree.

Using trie will help us to save time and space.
 

A sample trie formed by adding words ‘ate’, ‘ant’, ‘ants’, ‘bat’, ‘ball’, ‘and’ is shown below. The nodes with green color represent the end of the word. 

To know more about tries, click here. 
 

Algorithm: 

• Generate a trie by adding the words of the dictionary. The last letter of each word should be marked as the terminal or end of the word.
• After trie is built, string ‘S’ can be easily compared letter by letter in the trie.
• Traverse the string ‘S’ from left to right:
  • If the current character is not present as the children of the root of the trie, return from here as we can’t break the given string in valid words.
  • If at any point, we encounter a leaf in the trie, we can assume that we have found a valid word in the dictionary.
    • If we reach the end of the string ‘S’, we will add the sentence formed by breaking the string ‘S’ to our output array.
    • Else, recursively try to break the remaining string.
• Return the output array containing all the possible sentences obtained from breaking the given string ‘S’.

O(26 * K * | word |), where K is the number of strings in the dictionary, and | word | is the length of a word in the dictionary.

In the worst case, for every word in the dictionary, we will create | word | nodes and every node will have an array of size 26 (to store the children of the node). Since there are K strings in the dictionary, the number of nodes will be O(K * | word |) and thus the total space complexity will be O(26 * K * | word |).

Recursion stack space of O(N) is also used. Thus, the final space complexity is O((26 * K * | word |) + N) = O(26 * K * | word |).

O(N * (2 ^ (N - 1)), where ‘N’ is the length of the sentence.

Time complexity would be, in the worst case, O(N * (2 ^ (N - 1))) when each substring of the sentence exists as a word in the dictionary like sentence = “xxx” and dictionary={“x”, “xx”, “xxx”}. We need to explore the possible combinations. While our map is avoiding many redundant function calls, but still this approach will also go in O(N * (2 ^ (N - 1))) in the worst case. Though the complexity of this approach is the same as the previous approach, yet this approach is better because the time taken to search for a word in the trie is much less than that in a hashset.

/*

    Time Complexity : O(N * (2 ^(N - 1))

    Space Complexity :  O(26 * K * | word |)



    Where N is the length of string 'S', 'K' is the number of words in the dictionary and | word | is the length of each word. 

    

*/



class TrieNode

{



public:

    TrieNode *children[26];

    bool isTerminal;



    TrieNode()

    {

        // Setting all children of a new trie node to NULL

        for (int i = 0; i < 26; i++)

        {

            children[i] = NULL;

        }

        this->isTerminal = false;

    }

};



void insert(TrieNode *root, string word)

{

    TrieNode *curr = root;

    for (int i = 0; i < word.size(); i++)

    {

        // Expanding the Trie if the branch was not there yet

        if (curr->children[word[i] - 'a'] == NULL)

        {

            curr->children[word[i] - 'a'] = new TrieNode();

        }

        curr = curr->children[word[i] - 'a'];

    }

    // Mark last node as leaf

    curr->isTerminal = true;

}



void search(TrieNode *root, string &s, vector &res, string temp, int pos)

{

    TrieNode *curr = root;



    for (int i = pos; i < s.size(); i++)

    {

        if (curr->children[s[i] - 'a'] == NULL)

        {

            return;

        }

        if (curr->children[s[i] - 'a']->isTerminal == true)

        {

            // Last word we found with a positive lookup

            string lastWord = temp;

            lastWord.append(s.substr(pos, i - pos + 1));



            // If it is also the last character of s, update res

            if (i == s.size() - 1)

            {

                res.push_back(lastWord);

            }

            // Recursive calls otherwise

            else

            {

                search(root, s, res, lastWord + " ", i + 1);

            }

        }

        curr = curr->children[s[i] - 'a'];

    }

    return;

}



vector wordBreak(string &s, vector &dictionary)

{

    // Base Trie

    TrieNode *root = new TrieNode();



    // Add dictionary words into trie

    for (int i = 0; i < dictionary.size(); i++)

    {

        insert(root, dictionary[i]);

    }



    // Computing the final result

    vector res;

    search(root, s, res, "", 0);



    return res;

}

'''

    Time Complexity : O(N * (2 ^(N - 1))

    Space Complexity :  O(26 * K * | word |)



    Where N is the length of string 'S', 'K' is the number of words in the dictionary and 

    | word | is the length of each word. 

'''





class TrieNode:



    def __init__(self):



        # Setting all children of a new trie node to None

        self.children = [None for i in range(26)]

        self.isTerminal = False





def insert(root, word):



    curr = root

    for i in range(len(word)):



        # Expanding the Trie if the branch was not there yet

        if (curr.children[ord(word[i]) - ord('a')] == None):

            curr.children[ord(word[i]) - ord('a')] = TrieNode()



        curr = curr.children[ord(word[i]) - ord('a')]



    # Mark last node as leaf

    curr.isTerminal = True





def search(root, s, res, temp, pos):



    curr = root



    for i in range(pos, len(s)):



        if (curr.children[ord(s[i]) - ord('a')] == None):

            return



        if (curr.children[ord(s[i]) - ord('a')].isTerminal == True):



            # Last word we found with a positive lookup

            lastWord = temp

            lastWord += s[pos: i + 1]



            # If it is also the last character of s, update res

            if (i == len(s) - 1):

                res.append(lastWord)



            # Recursive calls otherwise

            else:

                search(root, s, res, lastWord + " ", i + 1)



        curr = curr.children[ord(s[i]) - ord('a')]



    return





def wordBreak(s, dictionary):



    # Base Trie

    root = TrieNode()



    # Add dictionary words into trie

    for i in range(len(dictionary)):

        insert(root, dictionary[i])



    # Computing the final result

    res = []

    search(root, s, res, "", 0)



    return res

/*

    Time Complexity : O(N * (2 ^(N - 1))

    Space Complexity :  O(26 * K * | word |)



    Where 'N' is the length of string 'S', 'K' is the number of words in the dictionary and | word | is the length of each word. 

*/



import java.util.ArrayList;



class TrieNode 

{

    TrieNode[] children;

    boolean isTerminal;



    TrieNode() 

    {

        children = new TrieNode[26];

        isTerminal = false;

        for (int i = 0; i < 26; i++)

            children[i] = null;

    }

}



public class Solution 

{



    public static void insert(TrieNode root, String word) 

    {

        TrieNode curr = root;



        for (int i = 0; i < word.length(); i++) 

        {

            // Expanding the Trie if the branch was not there yet

            if (curr.children[word.charAt(i) - 'a'] == null) 

            {

                curr.children[word.charAt(i) - 'a'] = new TrieNode();

            }



            curr = curr.children[word.charAt(i) - 'a'];

        }



        // Mark last node as leaf

        curr.isTerminal = true;

    }



    public static void search(TrieNode root, String s, ArrayList res, String temp, int pos) 

    {

        TrieNode curr = root;



        for (int i = pos; i < s.length(); i++) 

        {

            if (curr.children[s.charAt(i) - 'a'] == null) 

            {

                return;

            }

            if (curr.children[s.charAt(i) - 'a'].isTerminal == true) 

            {

                // Last word we found with a positive lookup

                String lastWord = temp;

                lastWord += (s.substring(pos, i + 1));



                // If it is also the last character of s, update res

                if (i == s.length() - 1) 

                {

                    res.add(lastWord);

                }

                

                // Recursive calls otherwise

                else 

                {

                    search(root, s, res, lastWord + " ", i + 1);

                }

            }



            curr = curr.children[s.charAt(i) - 'a'];

        }

        return;

    }



    public static ArrayList wordBreak(String s, ArrayList dictionary) 

    {

        // Base Trie

        TrieNode root = new TrieNode();



        // Add dictionary words into trie

        for (int i = 0; i < dictionary.size(); i++) 

        {

            insert(root, dictionary.get(i));

        }



        // Computing the final result

        ArrayList res = new ArrayList<>();

        search(root, s, res, "", 0);



        return res;

    }

}