[LeetCode 139] Word Break - Woodstock Blog

Question

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

Stats

Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a standard DP question.

Solution

I see a lot of people solve this DP problem with 2D array. It actually requires only 1D aray.

Declare an boolean array of (input string length) + 1, and dp[i] mean whether or not subtring(0,i) is work-breakable. Then the problem is clear and easy.

Pay attention to index while coding.

Code

my code

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