class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        /* Q58 of dp , every cell will store total no.of sentences which can be
        made using ith string , we have solved this question for total no. of 
        sentences which can be made from s for words in dictionary
        */

        HashSet<String> set = new HashSet<>(wordDict);
        int n = s.length();
        int[] dp = new int[n];

        for(int i =0 ; i < n ;i++){
            //checking all suffix of ith string
            for(int j = 0 ; j <= i  ; j++){
                String temp = s.substring(j , i+1);

                //if ith string is in dictionary 
                if(set.contains(temp)){
                    /* if the suffix word is in dictionary add that word in the
                    of all sentences which are made by dp[j-1];
                    */
                    if(j > 0)
                    dp[i] += dp[j-1];

                    //if the whole substring exist in the dictionary add +1 for
                    //that individual word
                    else //j==0
                    dp[i] += 1;
                }
            }
        }

        //if dp[n-1] has any valid sentences it will be greater than 0
        return dp[n-1] > 0 ? true : false;
    }
}