Leetcode 139: WordBreak

https://leetcode.com/problems/word-break/

DP Idea

You create a boolean array `f` of length `len(s)+1`. “`f[i] == True`” means substring `s[0:i-1]` can be matched successfully.

Jave code (Ref: https://leetcode.com/discuss/18904/java-implementation-using-dp-in-two-ways): 

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {

        boolean[] f = new boolean[s.length() + 1];
        Arrays.fill(f, false);

        f[0] = true;

        //Second DP
        for(int i=1; i <= s.length(); i++){
            for(int j=0; j < i; j++){
                if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }

        return f[s.length()];
    }
}

This algorithm takes O(N^2) time complexity and O(N) space.

Python Code Using DP (Ref: https://leetcode.com/discuss/23605/simple-dp-solution-in-python-with-description)

def word_break(s, words):
    d = [False] * len(s)    
    for i in range(len(s)):
        for w in words:
            if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
                d[i] = True
    return d[-1]

This algorithm improves the time complexity to O(NK) but still uses O(N) space.

Another improved Python Code

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
  
        break_idx = []
        for i in xrange(len(s)):
            if s[0:i+1] in wordDict:
                break_idx.append(i)
            else:
                for b in break_idx:
                    if s[b+1:i+1] in wordDict:
                        break_idx.append(i)
                        break
        
        return len(break_idx)>0 and break_idx[-1]== len(s)-1

This algorithm works better if you know there are only a few positions in `s` that can be segmented into words. (i.e., you know d[i]==True for only a small number of i, in the previous algorithm)

BFS Idea:

https://leetcode.com/discuss/8479/a-solution-using-bfs

But it is essentially similar to the DP idea. The time complexity is O(N^2).

Code

from collections import deque

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        l = deque([0])
        visited = set()
        while l:
            n = l.popleft()
            for word in wordDict:
                start = n
                end = start + len(word)
                if s[start:end] == word and end not in visited:
                    if end == len(s):
                        return True
                    l.append(end)
                    visited.add(end)
        
        return False

You can also use Trie (prefix tree) to solve this problem. (TODO)