C ++中的拼图前后
假设我们有一个短语列表，生成一个“之前和之后”难题列表。这里的短语是仅由小写字母和空格组成的字符串。开始和结束位置将没有空间。短语中没有连续的空格。
之前和之后的谜题是通过合并两个短语而形成的短语，其中第一个短语的最后一个单词与第二个短语的第一个单词相同。我们必须找到可以由每两个短语短语[i]和短语[j]组成的前拼图和后拼图，其中I！=j。请注意，匹配两个短语的顺序很重要，我们要考虑两个顺序。
我们应该找到按字典顺序排序的不同字符串的列表。因此，如果输入类似短语=["missionstatement","aquickbitetoeat","achipofftheoldblock", "chocolatebar","missionimpossible","amanonamission","blockparty","eatmywords","barofsoap"],
那么输出将是 ["achipofftheoldblockparty","amanonamissionimpossible","a
manonamissionstatement","aquickbitetoeatmywords","chocolate
barofsoap"].
为了解决这个问题，我们将遵循以下步骤-
定义一个字符串数组ret，对短语数组进行排序
定义一个映射m，n：=短语数组的大小
对于I范围从0到n–1
s：=短语[i]，rspace：=从右侧开始的空格索引
将我插入到位于m的列表中（当rspace为null时，然后为s，否则找到s的子字符串，直到rspace+1]
对于I范围从0到n–1
v：=m[x]
对于范围从0到v的j
将短语[v[j]]+s的子字符串（最大x的大小）插入ret
如果v[j]不是我，那么
s：=短语[i]lspace：=左侧的空白索引
x：=当lspace为null时，则为s，否则，从0到lspace找到s的子字符串]
如果m以x为键
排序ret
删除ret的唯一性并返回ret
范例（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
vector <string> ret;
sort(phrases.begin(), phrases.end());
unordered_map <string, vector <int> > m;
int n = phrases.size();
for(int i = 0; i < n; i++){
string s = phrases[i];
auto rspace = s.rfind(' ');
m[rspace == string::npos ? s : s.substr(rspace + 1)].push_back(i);
}
for(int i = 0; i < n; i++){
string s = phrases[i];
auto lspace = s.find(' ');
string x = (lspace == string::npos? s : s.substr(0, lspace));
if(m.count(x)){
vector <int>& v = m[x];
for(int j = 0; j < v.size(); j++){
if(v[j] != i){
ret.push_back(phrases[v[j]] + s.substr(x.size()));
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
};
main(){
vector<string> v = {"mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"};
Solution ob;
print_vector(ob.beforeAndAfterPuzzles(v));
}输入值
["mission statement","a quick bite to eat","a chip off the old block","chocolate bar","mission impossible","a man on a mission","block party","eat my words","bar of soap"]
输出结果
[a chip off the old block party, a man on a mission impossible, a man on a mission statement, a quick bite to eat my words, chocolate bar of soap, ]