raghuvanshraj

140.cpp

Aug 2nd, 2021
972
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  *    author:   vulkan
  3.  *    created:  05.03.2020 02:41:45 PM
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. void _wordBreak(string s, int pos, unordered_set<string> &dict_set, pair<bool, vector<string>> *dp) {
  10.     if (s == "") {
  11.         return;
  12.     }
  13.  
  14.     if (dp[pos].first) {
  15.         return;
  16.     }
  17.  
  18.     int n = s.size();
  19.     if (pos == n) {
  20.         dp[pos].first = true;
  21.         dp[pos].second.push_back("");
  22.         return;
  23.     }
  24.  
  25.     for (int i = pos; i < n; ++i) {
  26.         string curr_substring = s.substr(pos, i - pos + 1);
  27.         if (dict_set.find(curr_substring) != dict_set.end()) {
  28.             _wordBreak(s, i + 1, dict_set, dp);
  29.             vector<string> curr_vector = dp[i + 1].second;
  30.             int m = curr_vector.size();
  31.             for (int j = 0; j < m; ++j) {
  32.                 if (curr_vector[j] == "") {
  33.                     dp[pos].second.push_back(curr_substring);
  34.                 } else {
  35.                     dp[pos].second.push_back(curr_substring + " " + curr_vector[j]);
  36.                 }
  37.             }
  38.         }
  39.     }
  40.  
  41.     dp[pos].first = true;
  42. }
  43.  
  44. vector<string> wordBreak(string s, vector<string>& dict) {
  45.     unordered_set<string> dict_set;
  46.     int m = dict.size();
  47.     for (int i = 0; i < m; ++i) {
  48.         dict_set.insert(dict[i]);
  49.     }
  50.  
  51.     int n = s.size();
  52.     pair<bool, vector<string>> *dp = new pair<bool, vector<string>>[n + 1]();
  53.     for (int i = 0; i < n + 1; ++i) {
  54.         dp[i].first = false;
  55.     }
  56.  
  57.     _wordBreak(s, 0, dict_set, dp);
  58.  
  59.     return dp[0].second;
  60. }
  61.  
  62. int main(int argc, char const *argv[]) {
  63.     string s;
  64.     cin >> s;
  65.  
  66.     int m;
  67.     cin >> m;
  68.     vector<string> dict(m);
  69.     for (int i = 0; i < m; ++i) {
  70.         cin >> dict[i];
  71.     }
  72.  
  73.     vector<string> ans = wordBreak(s, dict);
  74.     for (int i = 0; i < ans.size(); ++i) {
  75.         cout << ans[i] << endl;
  76.     }
  77.  
  78.     return 0;
  79. }
RAW Paste Data