139. word splitting

To give you one character string s And a String list 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

reflection

Definition dp The meaning of array and its subscript

dp[i]: Express wordDict front 1-i Can a letter be made up of words

• dp[i] =1 , On behalf of 1-i Letters can be made up of words
• dp[i] = 0, conversely

initialization dp Array

establish dp[ s.length + 1] Array

Make dp[ 0 ] =1;

here dp[0] Yes, it plays an auxiliary role , The main purpose is to make dp[i-word.lenth] , Its i =word.length when ,dp = 1;

State transition equation

Here if dp[i-word.length] = 1, And the words and word identical dp[i]=1

class Solution {
    
    public boolean wordBreak(String s, List<String> wordDict) {
    
        // step 1  establish dp Array 
        int[] dp=new int[s.length()+1];

        // step 2  initialization dp Array 
        dp[0] =1;

        // step 3  perfect dp Array 
        for (int i=1;i<dp.length;i++){
    
            for (String word : wordDict) {
    
                if(i>=word.length()){
    
                    if (dp[i-word.length()]==0) continue;
                    String sub=s.substring(i-word.length(),i);
                    if(sub.equals(word)) {
    
                        dp[i]=1;
                        break;
                    }
                }
            }
        }

        // step 4 printDp
        for (int i = 0; i < dp.length; i++) {
    
            System.out.println("dp "+i+","+dp[i]);
        }
        if (dp[dp.length-1]==1) return true;
        else return false;
    }
}