Tìm từ ghép nối trong C++

Cho danh sách các từ khác nhau, tìm tất cả các từ ghép nối — tức là từ có thể tạo thành bằng cách nối ít nhất hai từ ngắn hơn trong cùng danh sách.

Ví dụ

Danh sách: ["cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"]

Kết quả: ["cowsgoatcows", "goatcowsgoat", "deercowgoatcow"]

Thuật toán: Trie + DP + Sắp xếp theo độ dài

1. Sắp xếp danh sách từ theo độ dài tăng dần.
2. Duyệt từng từ theo thứ tự:
   • Kiểm tra xem từ hiện tại có thể chia thành các từ đã thấy trước đó (đã chèn vào Trie) không — dùng DFS + memoization (mảng dp).
   • Nếu có → thêm vào kết quả.
   • Nếu không → chèn từ này vào Trie để dùng cho các từ dài hơn sau này.

Lý do sắp xếp: Khi xét từ dài, các từ thành phần ngắn hơn chắc chắn đã được chèn vào Trie.

Cài đặt C++

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

void print_vector(vector<string> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

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 (char x : s) {
            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 (string curr : words) {
            if (curr.empty()) continue;
            vector<int> dp(curr.size(), -1);
            if (isPresent(curr, head, 0, dp)) {
                ret.push_back(curr);
            } else {
                insertNode(head, curr);
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<string> v = {"cow", "cows", "cowsgoatcows", "goat", "goatcowsgoat", "hippopotamuses", "deer", "deercowgoatcow"};
    print_vector(ob.findAllConcatenatedWordsInADict(v));
    return 0;
}

Độ phức tạp

• Thời gian: O(N * L^2) — N từ, mỗi từ dài tối đa L, DFS với memo tránh tính toán lặp.
• Không gian: O(N * L) cho Trie và mảng DP.

Input / Output

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