2.18 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".

Method

when we want to know whether this string can be segmented in to sequence of one or more dictionary words,it is a combination of how many sequences of words it can be segmented. But we can seen that the result is depends on previous, if we split s into s1, s2. s2 is in dictionary, while s1 is not, then this segment is not. So if we check s1 not in, we do not need to search s2. So we can do it repeated. For index i, we can check from 0 - i, whether there has substring in dictionary, if all not ,thus i is not position for segment. it at index j, the 0- j is , we can check j - i , we just need a boolean[] to store the information for 0-j states

Time and Space Complexity

o(nl^2)

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];
}

}