[LeetCode] Word Break

Problem

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

First scan, mark every possible string section.

Second scan, dynamic programming,  for every string 0~i, it is a valid break-able string only if its previous string 0~j and new part j+1~ i are both valid words in the dictionary.

 


class Solution {  
 public:  
      bool wordBreak(std::string s, std::unordered_set<std::string> &dict) {  
           int n = s.size();  
           if(n==0||dict.size()==0)  
                return false;  
           std::vector<std::vector<bool>> map(n+1, std::vector<bool>(n+1, false));  
           map[0][0] = true;  
           std::vector<bool> memo(n+1, false);  
           memo[0] = true;  
           std::string tmp;  
           for(int i=0; i<n; i++)  
           {  
                for(int j=i; j<n; j++)  
                {  
                     tmp = s.substr(i, j-i+1);  
                     if(dict.find(tmp)!=dict.end())  
                          map[i+1][j+1]=true;  
                }  
           }  
           for(int i=0; i<n; i++)  
           {  
                for(int j=0; j<=i; j++)  
                {  
                     if(memo[j+1-1]&&map[j+1][i+1])  
                          memo[i+1] = true;  
                }  
           }  
           return memo[n];  
      }  
 };