6ms c++ solution, dp and dfs


  • 0
    class Solution {
     private:
      vector<int> dp;
      vector<string> cur, res;
    
      vector<int> check(string s, unordered_set<string>& wordDict, int max_l) {
        int n = s.size();
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        // dp[n] --> str(0..n-1) can break
        for (int i = 0; i < n; i++)
          for (int j = i; j >= 0; j--) {
            if (i - j + 1 > max_l) break;
    
            if (dp[j] && wordDict.count(s.substr(j, i - j + 1))) {
              dp[i + 1] = 1;
              break;
            }
          }
        return dp;
      }
    
      void create(string s, unordered_set<string>& dic, int max_l) {
        int size = s.size();
        for (int i = size - 1; i >= 0; i--) {
          if (size - i > max_l) break;
          if (dic.count(s.substr(i)) && dp[i]) {
            cur.push_back(s.substr(i));
            if (i == 0) {  // reach the head of the string
              string t;
              t += cur.back();
              for (int i = (int)cur.size() - 2; i >= 0; i--) t += " " + cur[i];
              res.push_back(t);
            } else
              create(s.substr(0, i), dic, max_l);
    
            cur.pop_back();
          }
        }
      }
    
     public:
      vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
        res.clear();
        cur.clear();
        int max_l = 0;
        for (auto& x : wordDict) max_l = max(max_l, (int)x.size());
    
        dp = check(s, wordDict, max_l);
        create(s, wordDict, max_l);
        return res;
      }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.