C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-11-01

#include<bits/stdc++.h>
using namespace std;
vector<vector<string>> res;
void DFS(string& s,vector<string>& dict_s,int start,vector<string> ans){
    if(start>=s.size()){
        res.push_back(ans);
        return;
    }
    string dict;
    bool flag=true;
    for(int i=dict_s.size()-1;i>=0;i--){
        dict=dict_s[i];
        if(start+dict.size()>s.length()){
            continue;
        }
        flag=true;
        for(int j=0;j<dict.size();j++){
            if(dict[j]!=s[start+j]){
                flag=false;
                break;
            }
        }
        if(flag){
            ans.push_back(dict);
            DFS(s,dict_s,start+dict.size(),ans);
            ans.pop_back();
        }
    }
}
int main(){
    string s,dict_s;
    getline(cin,s);
    getline(cin,dict_s);
    int index1=s.find_first_of('"');
    int index2=s.find_last_of('"');
    s=s.substr(index1+1,index2-index1-1);
    vector<string> v;
    for(int i=0;i<dict_s.size();i++){
        if(dict_s[i]=='"'){
            string dict="";
            i++;
            while(dict_s[i]!='"'){
                dict+=dict_s[i];
                i++;
            }
            v.push_back(dict);
        }
    }
    vector<string> ans;
    cout<<'[';
    DFS(s,v,0,ans);
    for(int i=0;i<res.size();i++){
        if(i==0){
            cout<<res[i][0];
            for(int j=1;j<res[i].size();j++){
                cout<<' '<<res[i][j];
            }
        }else{
            cout<<",";
            for(int j=0;j<res[i].size();j++){
                cout<<' '<<res[i][j];
            }
        }
    }
    cout<<']'<<endl;
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 384KB, 提交时间: 2021-07-26

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cstring> // 导入C的标准库
#include <functional>
#include <algorithm>

using namespace std;
int main(void) {
  string s, dict;
  getline(cin, s);
  getline(cin, dict);
  
  int first = s.find_first_of('"');
  int last  = s.find_last_of('"');
  s = s.substr(first + 1, last - first - 1);
  
  first = dict.find('"');
  dict = dict.substr(dict.find('"'), dict.length() - first);
  
  char* saved = nullptr;
  char* tok = strtok_r(const_cast<char*>(dict.c_str()), ",", &saved);
  unordered_set<string> words;
  while (tok) {
    string word = string(tok);
    word = word.substr(1, word.length() - 2);
//     cout << "word = " << word << endl;
    
    words.emplace(word);
    tok = strtok_r(nullptr, ",", &saved);
  }
  
  const int n = s.length();
  vector<string> candidates;
  vector<vector<string>> answer;
  
  function<void(int)> backtracking_algorithm = [&](int position) {
    if (position == n)
      return answer.push_back(candidates);
    
    for (int i = position; i < n; ++i) {
      string ss = s.substr(position, i - position + 1); // ss == substring
      if (not words.count(ss)) continue;
      candidates.emplace_back(ss);
      backtracking_algorithm(i + 1);
      candidates.pop_back(); // backtracing ...
    }
  };
  
  backtracking_algorithm(0);
  if (not answer.empty()) {
    reverse(begin(answer), end(answer));
    
    cout << '[';
    for (auto it = begin(answer); it != end(answer); ++it) {  // 答案是由多个句子组成的
      vector<string>& sentence = *it;
      for (auto iter = begin(sentence); iter != end(sentence); ++iter) {  // 句子是由多个单词组成的
        cout << *iter;
        if (iter < end(sentence) - 1) cout << ' ';
      }
      if (it < end(answer) - 1) cout << ", ";
    }
    cout << ']';
  } else {
    cout << "[]";
  }
  
  return 0;
}