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 := phrases数组的大小

  • 对于I从0到n-1

    • s := phrases[i]，rspace := 从右侧的空格索引

    • 将I插入到m[如果rspace为空，则为s，否则找到s直到rspace+1的子字符串]位置的列表中。

  • 对于I从0到n-1

    • s := phrases[i]，lspace := 从左侧的空格索引

    • x := 如果lspace为空，则为s，否则找到s从0到lspace的子字符串

    • 如果m包含键x

      • v := m[x]

      • 对于j从0到v的大小

        • 如果v[j]不等于I，则

          • 将phrases[v[j]] + s的子字符串（直到x的大小）插入到ret中

  • 对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"]

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

[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, ]

更新于：2020年4月29日

105 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告