ก่อนและหลังปริศนาใน C++

สมมติว่าเรามีรายการวลี ให้สร้างรายการปริศนาก่อนและหลัง วลีนี้เป็นสตริงที่ประกอบด้วยตัวพิมพ์เล็กและช่องว่างเท่านั้น จะไม่มีที่ว่างในตำแหน่งเริ่มต้นและสิ้นสุด ไม่มีการเว้นวรรคติดต่อกันในวลี

ปริศนาก่อนและหลังเป็นวลีที่เกิดขึ้นจากการรวมสองวลีเข้าด้วยกันโดยที่คำสุดท้ายของวลีแรกเหมือนกับคำแรกของวลีที่สอง เราต้องหาปริศนา Before และ After ที่สามารถสร้างได้จากทุกสองวลี phrases[i] และ phrases[j] โดยที่ I!=j. โปรดทราบว่าลำดับของการจับคู่สองวลีมีความสำคัญ เราต้องการพิจารณาทั้งสองคำสั่ง

เราควรหารายการของสตริงที่แตกต่างกันซึ่งจัดเรียงตามพจนานุกรม ดังนั้นหากข้อมูลเข้าเป็นวลี =["พันธกิจ", "กัดกินด่วน", "เศษขนมปังออกจากตึกเก่า", "ช็อกโกแลตบาร์", "ภารกิจที่เป็นไปไม่ได้", "ชายผู้อยู่ในภารกิจ", " ปาร์ตี้บล็อก", "กินคำพูดของฉัน", "สบู่ก้อน"] จากนั้นผลลัพธ์จะเป็น:["ชิปออกจากปาร์ตี้บล็อกเก่า", "ชายในภารกิจที่เป็นไปไม่ได้", "ชายคนหนึ่งในพันธกิจ "," กัดกินคำฉันหน่อย ", "สบู่ช็อกโกแลตแท่ง"].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดอาร์เรย์ของสตริง ret จัดเรียงวลีอาร์เรย์

• กำหนดแผนที่ m, n :=ขนาดของอาร์เรย์วลี

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • s :=วลี[i], rspace :=ดัชนีของช่องว่างทางด้านขวา

  • แทรก I ลงในรายการที่วางไว้ที่ m[เมื่อ rspace เป็นโมฆะ จากนั้น s มิฉะนั้น ค้นหาสตริงย่อยของ s ถึง rspace + 1]

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • s :=วลี[i] lspace :=ดัชนีช่องว่างจากด้านซ้าย

  • x :=เมื่อ lspace เป็นโมฆะ จากนั้น s มิฉะนั้น ค้นหาสตริงย่อยของ s จาก 0 ถึง lspace]

  • ถ้า m มี x เป็นคีย์

    • v :=m[x]

    • สำหรับ j ในช่วง 0 ถึงขนาดของ v

      • ถ้า v[j] ไม่ใช่ฉัน แล้ว

        • แทรกวลี[v[j]] + สตริงย่อยของ s (จนถึงขนาด x) ลงใน ret

• เรียงลำดับ

• ลบเฉพาะ ret และ return 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, ]