Word Break

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

-------------------------------- thinking ----------------------------------------------------------------
At the beginning, I used recursive algorithm to solve the problem, and reach TLE. After reading the discussion, dp is a good method to go

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        bool dp[s.size() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {
            for (int j = i-1; j >= 0; j--) {
                if (dp[j]) {
                    if (dict.find(s.substr(j, i-j)) != dict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
                dp[i] = false;
            }
        }
        return dp[s.size()];
    }
};
-----------------------------------------------------------------------------------------------------------
if dp[0] is not considered as empty string, then the length of dp should be s.size(), and the codes will be like below

class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        bool dp[s.size()];
        if (dict.find(s.substr(0, 1)) != dict.end()) {
            dp[0] = true;
        } else {
            dp[0] = false;
        }
        for (int i = 1; i < s.size(); i++) {
            dp[i] = false;
            if (dict.find(s.substr(0,i+1)) != dict.end()) {
                dp[i] = true;
                //bug
                //break;
            }
            for (int j = i-1; j >= 0; j--) {
                if (dp[j]) {
                    if (dict.find(s.substr(j+1, i-j)) != dict.end()) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()-1];
    }
};

------------------------------------ another dfs method ------------------------------------------------

class Solution:
# @param s, a string
# @param dict, a set of string
# @return a boolean
def wordBreak(self, s, words):
    stack, visited = list(), set()
    length = len(s)
    for i in range(1, length+1):
        if s[:i] in words:
            stack.append(i)
            visited.add(i)
    while stack:
        pos = stack.pop()
        if pos == length:
            return True
        for i in range(pos, length+1):
            if i not in visited and s[pos:i] in words:
                stack.append(i)
                visited.add(i)
    return False

use a set to store the position already searched

It seems test cases suit for dfs and no need to import deque