139. Word Break

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
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Solution:

Method 1: DP

We want to know whether s_0,i can be break, where i = s.length() - 1.

For any given i, if we find a j that s_0,j can be break, and s_j,i is in the dictionary. We know s_0,i can be break.

The time complexity is O(n³) and the space complexity is O(n).



Code:

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s == null || s.length() == 0) {
            return false;
        }
        
        // canbreak[i]: first i characters can be break
        boolean[] canbreak = new boolean[s.length() + 1];
        canbreak[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (canbreak[j] && wordDict.contains(s.substring(j, i))) {
                    canbreak[i] = true;
                    break;
                }
            }
        }
        return canbreak[s.length()];
    }
}

Method 2: BFS

We use BFS to search a valid cut.

If we can cut at index i, we offer it into the queue.

Each time we poll an index from the queue and try from this index.

If we find we reach the end of the string, we know there is a valid cut.



Code:

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        boolean[] visited = new boolean[s.length()];
        while (!queue.isEmpty()) {
            int start = queue.poll();
            if (!visited[start]) {
                for (int i = start + 1; i <= s.length(); i++) {
                    if (wordDict.contains(s.substring(start, i))) {
                        if (i == s.length()) {
                            return true;
                        }
                        queue.offer(i);
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
}