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

最先的想法就是brute force的一个一个试,用recursive的方法,但是速度太慢。Exceed Time Limit

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s.length() == 0) // if search has ended, return true;
            return true;
        for (int i = 0; i <= s.length(); i++)
        {
            if (dict.contains(s.substring(0, i)) && wordBreak(s.substring(i, s.length()), dict))
            {
                    return true;
            }
        }
        return false;
    }
}

用DP的方法,使用一个一维的boolean数组dp[0:s.length()]来记录是否[0:i]可以从字典中break word出来。最后dp[0:s.length()]的值就是结果了。
计算方法如下:
1.dp所有值初始化为false
2.从0开始每个dp开始扫描,如果s的0:i的String存在于字典中,那么dp[i]设为true.
3.对于一个设为true的dp的值,扫描整个字典,如果字典里的word和以i开始的substring相等 (只需要比和word长度相等的那个substring),就将dp[i+word.length]的值设为true

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if (s.length() == 0) 
            return true;
        if (dict.size() == 0)
            return false;
        boolean [] dp = new boolean [s.length() + 1]; // substring is exclusive on the max bountary
        for (int i = 1; i <= s.length(); i++)
        {
            if (dict.contains(s.substring(0, i)) || dp[i] == true)
            {
                dp[i] = true;
                for(String word : dict)
                {
                    if (i+word.length() > s.length())
                        continue;
                    if (s.substring(i, i+word.length()).equals(word))
                        dp[i+word.length()] = true;
                }
            }
        }
        return dp[s.length()];
    }
}

第二次提交code

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        boolean [] dp = new boolean [s.length()+1]; // if string before this char (exclusive) can be seperated in to words in dictionary
        dp[0] = true; //test substring(0, i) first
        int curr = 0;
        while(curr < s.length()) {
            if (dp[curr])
                for(String st : dict) {
                    if (st.length() + curr <= s.length() && st.equals(s.substring(curr, curr + st.length()))) {
                        dp[curr + st.length()] = true;
                        if (curr + st.length() == s.length())
                            return true;
                    }
                }
            curr++;
        }
        return false;
    }
}

\

The other way is to scan the string instead of scan the dictionary, which might be more realistic when the word length is short while the dictionary is large, still runs O(n^2) where n is the length of the string.

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

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