C++ 中的前后谜题
假设我们有一个短语列表，生成一个前后谜题列表。这里的短语是一个仅由小写字母和空格组成的字符串。起始和结束位置没有空格。短语中没有连续的空格。
前后谜题是通过合并两个短语形成的短语，其中第一个短语的最后一个单词与第二个短语的第一个单词相同。我们必须找到可以由每两个短语 phrases[i] 和 phrases[j] 形成的前后谜题，其中 I!= j。请注意，匹配两个短语的顺序很重要，我们要考虑这两个顺序。
我们应该找到按字典顺序排序的不同字符串列表。因此，如果输入类似 phrases = ["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"]。
为了解决这个问题，我们将遵循以下步骤 −
定义一个字符串数组 ret，对 phrases 数组进行排序
定义一个映射m, n := 短语数组的大小
对于 I 在 0 到 n – 1 的范围内
s := phrases[i], rspace := 从右侧开始的空格索引
将 I 插入到位于 m 处的列表中[当 rspace 为空时，则插入 s，否则查找 s 的子字符串，直到 rspace + 1]
对于 I 在 0 到 n 的范围内 – 1
s := phrases[i] lspace := 从左侧开始的空格索引
当 lspace 为空时，x := s，否则从 0 到 lspace 找到 s 的子字符串]
如果 m 以 x 为键
v := m[x]
对于 j，范围从 0 到 v 的大小
如果 v[j] 不是 I，则
将 phrases[v[j]] + s 的子字符串(最大到 x 的大小)插入到 ret 中
sort 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, ]
