leetcode解题: Word Break (139)

发表于 | 分类于

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given

1
2
s = "leetcode",
dict = ["leet", "code"].

Return true because “leetcode” can be segmented as “leet code”.

解法1：DP O(N^2)

经典的用DP的问题，用一个dp数组来记录。dp[i]表示前i个字符是否可能分词。
所以对于每一个dp[i], dp[i] = true if word(0,i) in dict, or dp[k] = true && word(k, i) in dict
这题的坑在于java的substring比较坑，string.substring(j,k)表示从第j个字符到第k-1个字符所组成的substring。
我们这里需要用word(k,i)表示的是第k+1个字符到第i-1个字符。这里容易出错需要注意一下。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        
        if (s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0) {
            return false;
        }
        
        // convert to set
        Set<String> set = new HashSet<String>();
        for (String word: wordDict) {
            set.add(word);
        }
        
        
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            if (set.contains(s.substring(0,i))) {
                dp[i] = true;
            } else {
                for (int j = 0; j < i; ++j) {
                    if (dp[j] && set.contains(s.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        
        return dp[s.length()];
        
    }
}