Word break problem dynamic programming

Word break dynamic programming problem

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. By space segmented means if we can reach the end of the string, because if the string can be broken into any dictionary words only then we can reach the end

Why this is a dp problem - because we are asked to break the string into words, at each step we are making a sub problem

2. While using dynamic programming trick here is to run the second loop only till we reach the first loop end this way we can control the total string we are reading to match the word
3. Where is dp here ? Each time you loop, you would be checking if you found the word, if you did then you would store that as true in the array, the index becomes true, next time you iterate you need not check that word again, hence it saves cycles
   Finally, ithis way you would reach the end and also genenrate any possible combinations which occur. So this code can be used to count the number of of words that occur from the given string(substring)
4. Hand drawn diagram to explaining the recursion

      private boolean wordBreak(String s, String dict[]) {
        HashSet<String> dictSet = new HashSet<>();
        boolean[] dp = new boolean[s.length() + 1];
        for(int i=0; i < dict.length; i++) {
            dictSet.add(dict[i]);
        }
        //we are controlling the length of the string in this way and we dont need to reset the loop again
        for (int i=1; i<dict.length; i++) {
            for (int j=0; j<i; j++) {
                if(dictSet.contains(s.substring(j, i)) && dp[j] == false) {
                        dp[i] = true;
                    //because i is the end value, the index we find the string part of, dict we update it as true
                    }
                }
            }
      return dp[s.length()];
    }