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, givens = "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.

• 解析

class Solution {public:    bool wordBreak(string s, vector
    
     & wordDict) {        set
     
       strset(wordDict.begin(), wordDict.end());//vector-->set        if (wordDict.size() == 0)        {            return false;        }        //动态规划        vector
      
        dp(s.size() + 1, false);        dp[0] = true;        for (int i = 1; i <= s.size(); i++) //第一层遍历，s的每个位置是否可分成字典元素        {            for (int j = i - 1; j >= 0; j--)            {                if (dp[j]) //j之前的元素可以分成字典元素                {                    if (strset.find(s.substr(j, i - j)) != strset.end())                    {                        dp[i] = true;                        break;                    }                }            }        }        return dp[s.size()];    }};
      
     
    

• bfs

bool wordBreak(string s, unordered_set
    
      &dict) {    // BFS    queue
     
       BFS;    unordered_set
      
        visited;        BFS.push(0);    while(BFS.size() > 0)    {        int start = BFS.front();        BFS.pop();        if(visited.find(start) == visited.end())        {            visited.insert(start);            for(int j=start; j
      
     
    

• dfs

class Solution {public:    bool dfs(string s, int start, vector
    
     & wordDict,vector
     
      & visited){        if(start == s.size()) return true;        if(visited[start]) return false;        visited[start] = true;        for(string word:wordDict){            int len = word.size();            string w = s.substr(start,len);            int end = start+len;            if(end>s.size())continue;            if(w == word&&dfs(s,end,wordDict,visited)){                return true;            }        }        return false;    }    bool wordBreak(string s, vector
      
       & wordDict) {        vector
       
         visited(s.size(),false);        return dfs(s,0,wordDict,visited);;    }};
       
      
     
    

题目来源