daily pastebin goal
71%
SHARE
TWEET

Untitled

a guest Jan 18th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.    
  4.     struct vertex{
  5.         bool leaf;
  6.         map<char , int> to;
  7.         vertex() {
  8.             to.clear();
  9.             leaf=0;
  10.         }
  11.     };
  12.    
  13.     bool wordBreak(string s, vector<string>& wordDict) {
  14.         if (s.empty() || wordDict.empty()) return 0;
  15.         vector<vertex> trie;
  16.         trie.push_back(vertex());
  17.         for (int i=0; i<wordDict.size(); i++){
  18.             string ss = wordDict[i];
  19.             int v=0;
  20.             for (int j=0; j<ss.size(); j++){
  21.                 char c = ss[j];
  22.                 if (trie[v].to.count(c)==0){
  23.                     trie.push_back(vertex());
  24.                     trie[v].to[c] = trie.size()-1;
  25.                 }
  26.                 v = trie[v].to[c];
  27.             }
  28.             trie[v].leaf = 1;
  29.         }
  30.         int n = s.size();
  31.         s = "#"+s;
  32.         bool *dp = new bool[n+1];
  33.         for (int i=1; i<=n; i++) dp[i]=0;
  34.         dp[0]=1;
  35.         for (int i=0; i<n; i++){
  36.             if (dp[i]){
  37.                
  38.                 int v=0, j = i+1;
  39.                 while (trie[v].to.count(s[j])>0) {
  40.                    // cout << i << " " << j << " " << v << " " << trie[v].leaf << endl;
  41.                     v = trie[v].to[s[j]];
  42.                     dp[j]|=(trie[v].leaf);
  43.                    
  44.                     j++;
  45.                 }
  46.                
  47.                
  48.             }
  49.         }
  50.         return dp[n];
  51.        
  52.        
  53.        
  54.     }
  55. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top