[Leetcode][DP][Backtracking] Word Break II [Snapchat]

1. What
Break a word with space to form a sentence with each word in the dictionary
s= "catsanddog"
dict = ["cat", "cats", "and", "sand","dog"]
A solution is ["cats and dog", "cat sand dog"]
Record all solutions => use DFS
2. How
2-1 can split like this
c
ca
cat
cats
catsa
catsan
....
2-1 need a dict
hashset<String> contain() to check if word exist or not
2-2 solve
Thought 1. split a string and hashset each substring(word), too much possibilities
Thought 2. start from the first letter to see any match in Dict (hashSet contain)
2-3 Solution
Thought 2. would be more doable, start from the first letter and check
2-4 Algorithm
so start from index 0 (int start)
and the length of extension (int ext)
E.g., s = "catsanddog"
start = 0 and ext =0 => "c",  NOT FOUND
start = 0 and ext =1 =>"ca", NOT FOUND
start = 0 and ext =2 => "cat",        FOUND (reset start =0+2+1= 3)
"cat sanddog"
start = 3 and ext = 0=>"s", NOT FOUND
start =3 and ext =1=>"sa", NOT FOUND
start = 3 and ext =2 =>"san", NOT FOUND
start =3 and ext =3=> "sand",          FOUND(reset start  = 3+3+1 = 7)
"cat sand dog"
start = 7 and ext =0 => "d", NOT FOND
start = 7 and ext =1=>"do",NOT FOUND
start= 7 and ext =2=> "dog",       FOUND (reset start = 7+2+1 = 10 > length)

start > length => return to start =3 and ext =3 "sand"
start = 3 and  ext = 4 "sandd", NOT FOUND

start =3 and ext =5 (total > length) return to start =0 and ext =2 "cat"
start = 0 and ext =3 =>"cats", FOUND (reset start = 0+3+1 =4)
"cats anddog"
start =4 and ext =0=>"a" X
start =4 and ext =1=> "an" X
start=4 and ext =2 => "and" O (reset start = 4+2+1 =7)
"cats and dog"
start =7 and ext = 0 =>..
start = 7 and ext =2=>"dog", FOUND(reset start = 7+2+1 > length)
 return
..

public class Solution
{
    public List wordBreak(String s, Set wordDict)
    {
         List res = new ArrayList();
        // valid the input
        if ( s== null || s.length() == 0)
        {
            return res;
        }
         
        if ( check(s,dict) )
        {
            helper(s,dict,0,"",res);
        }
        return res;
    }
    // get part of string 
    private void helper(String s, Set dict, int start, String item, List res)
    {
        if ( start >= s.length )
        {
              res.add(item);
              return;
        }
        // the length of extension from the start 
        StringBuilder str = new StringBuilder();
        for ( int i = start ; i < s.length() ;i++)
        {
            str.append(s.charAt(i));
            // FOUND
            if (  dict.contains( str.toString(str) )  )
            {
                 String newItem = new String();
                 if (item.length() > 0)
                 { 
                      newItem = item+ " "+ str.toString();
                 } 
                 else 
                 {
                      newItem = str.toString();
                 }
                 // reset start and recurse
                 helper(s, dict, i+1, newItem, res);
            }
        }
    }

    //check s if in the dict 
    private boolean check(String s , Set dict)
    {
        // validate the input
        if ( s== null || s.length() == 0)
        {
            return true;
        }
        boolean[] res = new boolean[s.length()+1];
        res[0] = true;
        for (int i = 0 ; i < s.length();i++)
        {       
               StringBuilder str = new StringBuilder(  s.substring(0,i+!)  );
               for (int j = 0; j<= i; j++)
               {
                    if (res[j] && dict.contains(str.toString()))
                    {
                         res[i+1] = true;
                         break;
                    }
                    str.deleteCharAt(0);
               }
        }
        return res[s.length()];
    }
}