my dp solution with JAVA


  • 0
    M

    public boolean wordBreak(String s, List<String> wordDict) {
    // dp : dp i represent from 0 -i characters can be broken multiple string in dict
    // intial value : dp 0 = 0;
    // formula :exist k(0<=k < i) make between 0--k string can be broken and k -- i stirng is belongs to dict
    if(s== null || s.length()==0 || wordDict == null) return false;

        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for(int i = 0; i <= len; i++) {
            for(int k = 0; k < i; k++) {
                dp[i] = dp[k] && wordDict.contains(s.substring(k, i));
                if(dp[i]) {
                    break; // for the inner loop to jump out
                }
                //if(dp[i]) {
                //    return true;
                //}
            }
        }
        return dp[len];
    }

  • 0
    V

    When i==len, it seems that the s.substring(k,l) is out of index limit. I can't understand how this method works, could you explain it? thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.