C++의 퍼즐 전후

구 목록이 있다고 가정하고 Before 및 After 퍼즐 목록을 생성합니다. 여기서 구는 소문자와 공백만으로 구성된 문자열입니다. 시작 위치와 끝 위치에는 공백이 없습니다. 구문에 연속된 공백이 없습니다.

전후 퍼즐은 첫 번째 구의 마지막 단어가 두 번째 구의 첫 번째 단어와 동일한 두 개의 구를 병합하여 형성되는 구입니다. I!=j인 두 개의 구 구[i]와 구[j]로 구성할 수 있는 Before 및 After 퍼즐을 찾아야 합니다. 두 구문이 일치하는 순서가 중요하므로 두 순서를 모두 고려하고자 합니다.

사전순으로 정렬된 고유한 문자열 목록을 찾아야 합니다. 따라서 입력이 구문 =["미션 선언문", "간단히 먹기", "오래된 블록 칩 오프", "초콜릿 바", "미션 임파서블", "임무 중인 남자", " block party", "eat my words", "bar of soap"] 그러면 출력은 다음과 같습니다. ", "간단히 내 말을 먹기 위해", "초콜릿 비누"].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 문자열 배열 정의 ret, 구문 배열 정렬

• 맵 정의 m, n :=구 배열의 크기

• 0 ~ n – 1 범위의 I

  • s :=phrases[i], rspace :=오른쪽부터 공백 인덱스

  • m[rspace가 null이면 s, 그렇지 않으면 rspace + 1까지 s의 부분 문자열 찾기]

    에 있는 목록에 I를 삽입합니다.

• 0 ~ n – 1 범위의 I

  • s :=phrases[i] lspace :=왼쪽부터 공백 인덱스

  • x :=lspace가 null이면 s, 그렇지 않으면 0에서 lspace까지 s의 부분 문자열 찾기]

  • m이 키로 x인 경우

    • v :=m[x]

    • 범위 0에서 v 크기까지의 j에 대해

      • v[j]가 I가 아니면

        • 삽입구[v[j]] + s의 부분 문자열(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, ]