140-Word-Break-II

Problem Link : https://leetcode.com/problems/word-break-ii/
------------------------------------------------------------------
Complexity : Time - O(N^2), Memory - O(len of strings in Dictionary + length of string + length of map === N + N + N^2 === N^2)
------------------------------------------------------------------
Algorithm -
1. Convert the wordDict to Trie Data Structure.
2. Then traverse the whole string 's' in dfs manner and store the ans from ith place till nth in map
  2.i if already visited then get the ans from the map
  2.ii if not find the word in trie from that point if present send for other traversing and if not
      present that means that substring is not in wordDict so we put list in map and backtrack
      
3. Add the current word in all the strings of the list and see if other word is present in the same call then repeat step 2
--------------------------------------------------------------------

{
    Trie head;
    HashMap<Integer, List<String>> map;
    int[] dp;
    public List<String> wordBreak(String s, List<String> wordDict) {
        head=new Trie();
        map=new HashMap();
        dp=new int[s.length()+1];
        
        dp[s.length()]=1;// base value
        map.put(s.length(), new ArrayList());
        for(String str : wordDict)
            addString(str);// adding in trie
        
        traverse(0, s.toCharArray());
        return map.get(0);
    }
    private void addString(String str){
        Trie temp=head;
        int n=str.length();
        for(int i=0;i<n;i++){
            char ch=str.charAt(i);
            if(!temp.map.containsKey(ch))
                temp.map.put(ch, new Trie());
            temp=temp.map.get(ch);
        }
        temp.end=true;// seting the flag at the end of string 
    }
    private int traverse(int i, char[] s){
        if(dp[i]!=0)   // dp[i] can be -1, 0, 1 -1 = no ans present from this point, 0 = not visited yet, 1 = visited and ans present
            return dp[i];
        List<String> list=new ArrayList();
        int n=s.length;
        Trie trie=head;// Not to lost the head of the trie
        
        for(int i1=i;i1<n;i1++){
            if(!trie.map.containsKey(s[i1]))//if char not present that means that there is no word with s[i1] char so break
                break;
            trie=trie.map.get(s[i1]);
            if(trie.end){// end = true means a word ends at this point s.substring(i, i1+1)
                int ans=traverse(i1+1, s); // ans = -1/ 0/ 1 
                if(ans==1){// ans == 1 means ans already calculated and present
                    String str=getString(i, i1+1, s);
                    if(i1+1==n){// becoz this is the last index and no need for further traversing 
                        list.add(str);
                    } else {// add the currently find word with the i1+1 position result
                        addStrings(list, str, map.get(i1+1));
                    }
                }
            }
        }
        if(list.size()==0)// that means no result present from this point onward
            dp[i]=-1;
        else dp[i]=1;// result present
        map.put(i, list);
        
        return dp[i];
    }
    private String getString(int s, int e, char[] s1){
        StringBuilder str=new StringBuilder("");
        for(int i1=s;i1<e;i1++)
            str.append(s1[i1]);
        
        return str.toString();
    }
    private void addStrings(List<String> tar, String str, List<String> bucket){
        for(String s : bucket){
            tar.add(str+" "+s);
        }
    }
}
class Trie {
    HashMap<Character, Trie> map;
    boolean end;
    Trie(){
        map=new HashMap();
        end=false;
    }
}