LeetCode139—Word Break-蒲公英云

LeetCode139—Word Break

1.原题

原题链接

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

2.分析

网上主流的两种说法，DP和DFS，DP将来补充，自己用DFS写的。比如说：

s=”LeetCode” dict={“Leet”,”Code”}

就从s[0]开始，”L” ,”Le”, “Lee”,”Leet” 当找到匹配项时，重新设定起始位置，从剩下的子串开始搜索。

这个思路最后会超时。

不过可以记录一下，DFS返回时字符串中不满足条件的位置的索引添加到容器中。

代码

class Solution {
private:
    unordered_set<int>index;
    bool dfs(string s, unordered_set<string>&wordDict,int start)
    {
        if (start==s.size())//DFS返回
            return true;
        if (index.find(start) != index.end())//不满足条件的索引
            return false;
        for (int i = 1; i <= s.size()-start; i++)
        {
            string sub = s.substr(start, i);
            if (wordDict.find(sub) != wordDict.end())
            {
                if (dfs(s, wordDict, start+i))
                    return true;
                else
                    index.insert(start+i);//将不满足条件的索引添加到容器中
            }
        }
        return false;
    }
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        return dfs(s, wordDict,0);
    }
};