问题描述：给定一个字符串s=“catsanddog”, 给出一个字典dict={"cat", "cats", "and", "sand", "dog"}, 求能组成的句式有哪些。
例如s=“catsanddog”， dict={"cat", "cats", "and", "sand", "dog"}， sentences=["cat sand dog", "cats and dog"]。
分析：每一次遍历字符串找到与字典中的value对应的子串即可。
解题思路：先在字符串s中，找出字典值的所在子串的位置，根据子串的位置将字典值放入集合中，形成映射表。
然后再遍历映射表一次对字符串进行组合，生成可能的句式。每个单词的索引(offset)与单词长度(length)即为一下个单词的索引,
即next_offset=(offset + length), 则下一个应该遍历的映射表位置就是next_offset。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;// 创建一个字典的映射表
void
create_dict_map(map<int, vector<string>>& map_dict,string s_raw,vector<string> vs_dict) {vector<string> vs_allocer;for (int i = 0; i < vs_dict.size(); i++) {int offset = s_raw.find(vs_dict[i]);if (map_dict.find(offset) == map_dict.end())map_dict[offset] = vs_allocer;map_dict[offset].push_back(vs_dict[i]);}
}void
parttern(map<int, vector<string>> map_dict,int offset,int raw_len,vector<string>& vs_result,vector<string>& vs_ret_res,int& i_bool) {if (map_dict.begin() == map_dict.end())return;for (auto auto_temp : map_dict[offset]) {int i_dict_len = offset + auto_temp.length();if (i_dict_len == raw_len) {if (i_bool)vs_ret_res.push_back(", ");string s_res;for (int i = 0; i < vs_result.size(); i++)s_res += vs_result[i] + ' ';s_res += auto_temp;vs_ret_res.push_back(s_res);i_bool = 1;return;}vs_result.push_back(auto_temp);parttern(map_dict, i_dict_len, raw_len, vs_result, vs_ret_res, i_bool);vs_result.pop_back();}
}int main(int argc, char** argv) {string s;getline(cin, s);vector<string> vs_dict;string s_dict;cin >> s_dict;vs_dict.push_back(s_dict);while (getchar() == ' ') {cin >> s_dict;vs_dict.push_back(s_dict);}map<int, vector<string>> map_dict;create_dict_map(map_dict, s, vs_dict);vector<string> result;vector<string> vs_ret_res;int i_bool = 0;parttern(map_dict, 0, s.length(), result, vs_ret_res, i_bool);cout << "[";for (int i = vs_ret_res.size() - 1; i >= 0; i--)cout << vs_ret_res[i];cout << "]";system("pause");return 0;
}