Word Break

Description

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s = "leetcode", dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

Hint

Train of Thought

DP

Code

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
           if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0){
               return false;
           }
           int len = s.length();
           boolean[] f = new boolean[len + 1];
           f[0] = true;
           for (int i = 0; i <= len; i++){
               for (int j = 0 ; j < i; j++){
                   if (!f[j]){
                       continue;
                   }
                   String sub = s.substring(j ,i);
                   if (wordDict.contains(sub)){
                       f[i] = true;
                       break;
                   }
               }
           }
           return f[len];
    }
}

Complexity