Word splitting problem

subject ：

Give you a string s And a list of strings wordDict As a dictionary . Please judge whether you can use the words in the dictionary to splice s .

Be careful ： It is not required to use all the words in the dictionary , And the words in the dictionary can be reused .

Example 1：

Input : s = “leetcode”, wordDict = [“leet”, “code”]
Output : true
explain : return true
because “leetcode” Can be “leet” and “code” Stitching into .
Example 2：

Input : s = “applepenapple”, wordDict = [“apple”, “pen”]
Output : true
explain : return true
because “applepenapple” Can be “apple” “pen” “apple” Stitching into .
Be careful , You can reuse the words in the dictionary .
Example 3：
Input : s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output : false

Code ：

DP

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
       boolean[] dp = new boolean[s.length()+1];
       dp[0] = true;
       for(int i = 1; i <= s.length(); i++){    // knapsack 
           for(int j = 0; j < i; j++){          // goods           
               if(wordDict.contains(s.substring(j,i)) && dp[j]){
                   dp[i] = true;
               }
           }
       }
       return dp[s.length()];
    }
}

to flash back

   public boolean backTrack(String s, Set<String> wordDictSet, int startIndex, int[] memory){
        // Termination conditions 
        if(startIndex >= s.length()){
            return true;
        }
        if(memory[startIndex] != 0){
            return memory[startIndex] == 1 ? true:false;
        }

        // Processing results ,  recursive ,  to flash back 
        for(int i = startIndex; i < s.length(); i++){
            String word = s.substring(startIndex, i+1);
            if(wordDictSet.contains(word) && backTrack(s, wordDictSet, i+1, memory)){
                memory[startIndex] = 1;
                return true;
            }
        }
        memory[startIndex] = -1;
        return false;
    }