คำต่อกันใน C++ (Concatenated Words)

ภาพรวมปัญหา

ให้รายการคำที่ไม่ซ้ำกัน หาคำทั้งหมดที่เป็น "คำต่อกัน" (concatenated words) — คือคำที่ประกอบด้วยคำสั้นกว่าอย่างน้อย 2 คำจากในรายการเดียวกัน

ตัวอย่าง

Input: ["cow","cows","cowsgoatcows","goat","goatcowsgoat","hippopotamuses","deer","deercowgoatcow"]
Output: ["cowsgoatcows","goatcowsgoat","deercowgoatcow"]

วิธีแก้ปัญหา: Trie + DP + Memoization

เรียงคำตามความยาวสั้นไปยาว แล้วสร้าง Trie ทีละคำ สำหรับแต่ละคำ ตรวจสอบว่าสามารถแยกเป็นคำใน Trie ได้หรือไม่ โดยใช้ DP + Memoization

โครงสร้างข้อมูล

• Trie Node: มี isEnd (จบคำหรือไม่) และ child (map char → Node*)
• DP array: dp[i] = สามารถแยกคำจากตำแหน่ง i ถึงท้ายได้หรือไม่ (-1=ยังไม่คำนวณ, 0=ไม่ได้, 1=ได้)

ขั้นตอนหลัก

1. เรียงคำตามความยาว
2. สร้าง Trie ว่าง
3. สำหรับแต่ละคำ curr:
   • ถ้าคำว่าง → ข้าม
   • สร้าง DP array ขนาด curr.size() เติม -1
   • เรียก isPresent(curr, head, 0, dp) ตรวจสอบว่าแยกได้จากคำใน Trie หรือไม่
   • ถ้าได้ → เพิ่มในผลลัพธ์
   • ถ้าไม่ได้ → แทรก curr เข้า Trie (เพื่อให้คำยาวกว่าใช้ได้)

ฟังก์ชัน isPresent (Recursive + Memo)

bool isPresent(string str, Node* head, int idx, vector<int>& dp) {
    if (idx >= str.size()) return true;
    if (dp[idx] != -1) return dp[idx];
    Node* curr = head;
    bool ok = false;
    for (int i = idx; i < str.size(); i++) {
        char x = str[i];
        if (!curr->child[x]) break;
        curr = curr->child[x];
        if (curr->isEnd) ok |= isPresent(str, head, i + 1, dp);
    }
    return dp[idx] = ok;
}

โค้ด C++ เต็ม

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

struct Node {
    bool isEnd;
    map<char, Node*> child;
    Node() { isEnd = false; }
};

class Solution {
public:
    bool isPresent(string str, Node* head, int idx, vector<int>& dp) {
        if (idx >= str.size()) return true;
        if (dp[idx] != -1) return dp[idx];
        Node* curr = head;
        bool ok = false;
        for (int i = idx; i < str.size(); i++) {
            char x = str[i];
            if (!curr->child[x]) break;
            curr = curr->child[x];
            if (curr->isEnd) ok |= isPresent(str, head, i + 1, dp);
        }
        return dp[idx] = ok;
    }

    static bool cmp(string s1, string s2) { return s1.size() < s2.size(); }

    void insertNode(Node* head, string s) {
        Node* curr = head;
        for (int i = 0; i < s.size(); i++) {
            char x = s[i];
            if (!curr->child[x]) curr->child[x] = new Node();
            curr = curr->child[x];
        }
        curr->isEnd = true;
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        Node* head = new Node();
        sort(words.begin(), words.end(), cmp);
        vector<string> ret;
        for (int i = 0; i < words.size(); i++) {
            string curr = words[i];
            if (curr == "") continue;
            vector<int> dp(curr.size(), -1);
            if (isPresent(curr, head, 0, dp)) ret.push_back(curr);
            else insertNode(head, curr);
        }
        return ret;
    }
};

การวิเคราะห์ความซับซ้อน

• เวลา: O(N × L²) โดยประมาณ (N = จำนวนคำ, L = ความยาวคำเฉลี่ย)
• พื้นที่: O(จำนวนโหนดใน Trie + N × L)