C ++中的拼图前后

假设我们有一个短语列表，生成一个“之前和之后”难题列表。这里的短语是仅由小写字母和空格组成的字符串。开始和结束位置将没有空间。短语中没有连续的空格。

之前和之后的谜题是通过合并两个短语而形成的短语，其中第一个短语的最后一个单词与第二个短语的第一个单词相同。我们必须找到可以由每两个短语短语[i]和短语[j]组成的前拼图和后拼图，其中I！= j。请注意，匹配两个短语的顺序很重要，我们要考虑两个顺序。

我们应该找到按字典顺序排序的不同字符串的列表。因此，如果输入类似短语= ["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，对短语数组进行排序

• 定义一个映射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, ]