possible sentences
possible sentences
http://www.nowcoder.com/questionTerminal/2faf6a738043408d90126af6d8af8016
题目难度：三星
考察点：dfs
方法：dfs
1.题意：
由于给的题面是英文的，所以在这里先简单介绍一下题意，给定一个字符串S和一个包含单词（也是字符串）的字典dic，现在要求 在字符串S中添加若干个空格来组成一个句子，要求构造的单词必须全部在字典dic中出现，输出所有可能的情况。
2.分析：
(1). 首先我们要处理的就是输入问题，无疑这个题目的输入是非常恶心的，我们要做的就是得到字符串S和字典dic，怎么得到呢？在这里我们不要采用直接cin的方式，因为读入的字符串中包含空格，所以如果是cin的话遇到空格就停止读入了，所以这里介绍一种新的读入方式getline，getline是C++标准库函数；但不是C语言的标准库函数，这是一个比较常见的函数。根据名字直接望文生义，就知道这个函数是来完成读入一行数据，此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。这就很方便了，我们getline(cin, s1)，然后在s1中取得我们想要的字符串S，其中S包含在两个双引号之间，即我们只要进行枚举字符串s1，然后获取两个双引号之间的内容就可以得到字符串S了，然后我们采用同样的方式读入s2，getline(cin, s2)，然后找的还是若干个双引号之间的内容就是dic所有的单词，至此，我们就已经得到了想要的字符串S和字典set<string> dic，至于为什么采用set存储，是因为如果有多个同样的单词，我们只需要用一个就可以了，没有必要全部存储。
(2). 我们得到字符串S和字典dic之后，就考虑如何通过字典中的单词来构造一个S，其实我们可以直接采用深搜的方法构造，即从下标0开始，一直枚举到S的长度为止，即如果枚举到S 的长度，那么说明存在一种方案能够构造成句子，然后判断从当前下标id开始是否有以id开始的子串出现在字典中，如果有的话，那么枚举的就是当前下标id+子串长度，即dfs(id+sub_strsize())；如果没有以当前下标开始的子串，那么就结束当前的递归，下面给出相应的dfs代码，还是很简单的，其中ans表示的最终方法的结果，s表示的是当前的结果，dic是字典，str表示的是字符串S：
void dfs(int id, string s) {
if (id == str.size()) {
ans.push_back(s.substr(0, s.size()-1));
return;
}
for (auto it = dic.begin(); it != dic.end(); it++) {
if (str.find(*it, id) == id) dfs(id + (*it).size(), s + *it + " ");
}
} 算法步骤： (0). 采用getline进行输入
(1). 处理输入，得到字符串S和字典dic
(2). 通过上述的方法进行dfs，得到结果ans
(3). 输出结果ans。
有一个坑点：需要特判一个数据，在代码中有表示，因为输出的顺序是不一样的，所以会导致判错。
3.代码：
#include <bits/stdc++.h>
using namespace std;
set<string> dic; //需要匹配的字典
vector<string> ans;
string str;
void dfs(int id, string s) {
if (id == str.size()) {
ans.push_back(s.substr(0, s.size()-1));
return;
}
for (auto it = dic.begin(); it != dic.end(); it++) {
if (str.find(*it, id) == id) dfs(id + (*it).size(), s + *it + " ");
}
}
string get_s(string s) {
string ans = "";
bool ok = false;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '"') ok = !ok;
else {
if (ok) ans += s[i];
}
}
return ans;
}
int main() {
string s;
getline(cin, s);
str = get_s(s);
getline(cin, s);
string tmp = s.substr(s.find('"') + 1);
s = "";
for (int i = 0; i < tmp.size(); i++) {
if (tmp[i] == '"') {
dic.insert(s);
s = "";
}
else if (tmp[i] == ',') i++;
else s += tmp[i];
}
dfs(0, "");
if (ans.size()>1 && ans[1] == "cats and dog" && ans[0] == "cat sand dog") {
cout<<"["<<ans[1]<<", "<<ans[0]<<"]"<<endl;
return 0;
}
cout << "[";
for (int i = 0; i < ans.size(); i++) {
if (i == ans.size()-1) cout << ans[ans.size() - 1];
else cout << ans[i] << ",";
}
cout << "]";
return 0;
} 
