CPP   82

Word Break

Guest on 18th April 2022 06:42:41 AM

  1. class Solution {
  2. public:
  3.     bool wordBreak(string s, vector<string>& wordDict) {
  4.         int l = s.length();
  5.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
  6.         int f[l+1];
  7.         f[0] = 1;
  8.         for (int i=1; i<=l; i++) {
  9.             // meaningless to check case j==i
  10.             f[i] = false;
  11.             for (int j=0; j<i; j++) {
  12.                 if (f[j]==true && wordSet.find(s.substr(j,i-j))!=wordSet.end()) {
  13.                     f[i] = true;
  14.                     break;
  15.                 }
  16.             }
  17.         }
  18.         return f[l];
  19.        
  20.     }
  21. };

Raw Paste

Login or Register to edit or fork this paste. It's free.