หา Starting Indices ของ Substrings ที่ประกอบจากคำใน List ทั้งหมด (Concatenated Words) ใน C++

โจทย์: กำหนด string s และ list ของคำ words (ทุกคำยาวเท่ากัน) หา starting indices ทั้งหมดของ substring ใน s ที่เป็นการต่อกันของคำใน words ทุกคำครบถ้วน ไม่มีตัวอักษรแทรกแซง

ตัวอย่าง: s = "wordgoodgoodgoodword", words = ["word","good"] → indices [0, 12] เพราะ "wordgood" (index 0) และ "goodword" (index 12)

อัลกอริธึม (Sliding Window + Hash Map)

1. นับ frequency ของแต่ละคำใน words → wordCnt
2. window = words.size() * word_len
3. Sliding window ขนาด window บน s:
   • ตรวจสอบ substring ใน window ว่าแบ่งเป็นคำได้ครบตาม wordCnt (ฟังก์ชัน ok())
   • ถ้าผ่าน → บันทึก index
   • เลื่อน window 1 ตัวอักษร

ฟังก์ชัน ok(s, wordCnt, word_len)

• แยก s เป็น chunks ยาว word_len
• เช็คแต่ละ chunk ว่ามีใน wordCnt และยังเหลือ quota
• ลด quota หรือลบ key เมื่อครบ
• คืน true ถ้า wordCnt ว่างหมด

ตัวอย่างโค้ด 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:
    bool ok(string s, unordered_map<string, int> wordCnt, int n) {
        string temp = "";
        for (int i = 0; i < n; i++) temp += s[i];
        for (int i = n; i < s.size(); i++) {
            if (temp.size() % n == 0) {
                if (wordCnt.find(temp) == wordCnt.end()) return false;
                if (wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
                else { wordCnt[temp]--; temp = ""; }
            }
            temp += s[i];
        }
        if (wordCnt.find(temp) == wordCnt.end()) return false;
        if (wordCnt[temp] == 1) { wordCnt.erase(temp); temp = ""; }
        else { wordCnt[temp]--; temp = ""; }
        return wordCnt.size() == 0;
    }

    vector<int> findSubstring(string a, vector<string> &b) {
        if (a.empty() || b.empty()) return {};
        unordered_map<string, int> wordCnt;
        for (auto &w : b) wordCnt[w]++;
        vector<int> ans;
        int window = b.size() * b[0].size();
        string temp = "";
        for (int i = 0; i < window; i++) temp += a[i];
        for (int i = window; i < a.size(); i++) {
            if (temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
                ans.push_back(i - window);
            temp += a[i];
            if (temp.size() > window) temp.erase(0, 1);
        }
        if (temp.size() % window == 0 && ok(temp, wordCnt, b[0].size()))
            ans.push_back(a.size() - window);
        return ans;
    }
};

int main() {
    vector<string> v = {"word","good"};
    Solution ob;
    print_vector(ob.findSubstring("wordgoodgoodgoodword", v));
}

อินพุต

"wordgoodgoodgoodword", {"word","good"}

เอาต์พุท

[0, 12, ]

Complexity

• Time: O(N * L) โดย N = |s|, L = window size
• Space: O(W) โดย W = จำนวนคำ unique