Before and After Puzzle ใน C++ : สร้างวลีต่อเนื่องจากคำสุดท้ายและคำแรก

ให้ List ของ **Phrases** (วลี) แต่ละวลีประกอบด้วยตัวอักษรพิมพ์เล็กและ Space เท่านั้น ไม่มี Space นำหน้าหรือท้าย และไม่มี Space ซ้อนกัน

Before and After Puzzle คือ วลีใหม่ที่เกิดจาก **ต่อวลี 2 วลี** โดยที่ **คำสุดท้ายของวลีแรก = คำแรกของวลีที่สอง** (Order matters: พิจารณาทั้ง (i,j) และ (j,i))

หา **Distinct Strings** ทั้งหมด เรียง **Lexicographically**

ตัวอย่าง

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

Output:
[
  "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"
]

แนวทาง: Hash Map + String Matching

1. Sort Phrases ก่อน (เพื่อผลลัพธ์ Lexicographical ได้ง่าย)
2. สร้าง Map m[lastWord] = list of indices — Map คำสุดท้าย -> Indices ของวลีที่ลงท้ายด้วยคำนั้น
3. สำหรับแต่ละวลี i:
   • หา firstWord (คำแรก)
   • หาใน Map m[firstWord] -> ได้ Indices j ที่ลงท้ายด้วยคำนี้
   • ต่อวลี: phrases[j] + phrases[i].substr(firstWord.length())
   • เก็บเฉพาะ i != j
4. Sort ผลลัพธ์ + Unique

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        vector<string> ret;
        sort(phrases.begin(), phrases.end()); // 1. Sort for lexicographical output

        unordered_map<string, vector<int>> m;
        int n = phrases.size();

        // 2. Build map: lastWord -> indices
        for (int i = 0; i < n; i++) {
            string s = phrases[i];
            auto rspace = s.rfind(' ');
            string lastWord = (rspace == string::npos) ? s : s.substr(rspace + 1);
            m[lastWord].push_back(i);
        }

        // 3. Match firstWord with map
        for (int i = 0; i < n; i++) {
            string s = phrases[i];
            auto lspace = s.find(' ');
            string firstWord = (lspace == string::npos) ? s : s.substr(0, lspace);

            if (m.count(firstWord)) {
                for (int j : m[firstWord]) {
                    if (j != i) {
                        // Concatenate: phrase[j] + phrase[i] without duplicate firstWord
                        ret.push_back(phrases[j] + s.substr(firstWord.size()));
                    }
                }
            }
        }

        // 4. Sort & Unique
        sort(ret.begin(), ret.end());
        ret.erase(unique(ret.begin(), ret.end()), ret.end());
        return ret;
    }
};

Input / Output

Input:  ["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"]
Output: ["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"]

ความซับซ้อน (Complexity)

• Time: O(N * L log N + R log R) — N วลี, L ความยาวเฉลี่ย, R ผลลัพธ์
• Space: O(N * L)

หัวใจคือ **Map คำสุดท้าย -> Indices** และ **String Concatenation ตัดคำซ้ำ** ครับ