139. Word Break

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”.

思路:如果给定单词可以被分解,那么在字典中都可以找到对应的每一块, 我们需要找到这样的分割点。这里有一个条件那就是这个单词的最后一个分割点到单词末尾组成的substring肯定会出现在字典中,从这个分割点开始往前也是可以分解在字典中找到对应的单词。 我们可以用DP的思想来做这个题目, 从后往前来验证。 外层循环可以从后往前来挨个遍历单词每个字符,内层循环来找这样的分割点到单词末尾之间组成的所有substring是否有存在在字典当中。我们用一个boolean 数组来表示,某个点i到单词末尾组成的所有的可能的substring的集合是否有在Dict中出现过。依次从后往前找,直到最后返回数组第一个值即可。

复杂度: Time: O(n^2), Space: O(n)

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        Arrays.fill(dp, false);
        dp[s.length()] = true;
        for (int i = s.length() - 1; i >= 0; i--) {
            for(int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (wordDict.contains(sub) && dp[j + 1]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[0];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s