Longest String Chain ใน C++

คำอธิบายปัญหา

กำหนดรายการคำ (words) ที่ประกอบด้วยตัวอักษรพิมพ์เล็ก คำ word1 ถือเป็น predecessor ของ word2 ก็ต่อเมื่อเราสามารถเพิ่มตัวอักษรได้เพียง 1 ตัวในตำแหน่งใดก็ได้ของ word1 เพื่อให้กลายเป็น word2 เช่น "abc" เป็น predecessor ของ "abac" Word chain คือลำดับคำ [word_1, word_2, ..., word_k] ที่ word_i เป็น predecessor ของ word_{i+1} ต้องการหาความยาวสูงสุดของ word chain ที่เป็นไปได้

ตัวอย่าง: ["a","b","ba","bca","bda","bdca"] → ผลลัพธ์ 4 (chain: "a" → "ba" → "bda" → "bdca")

วิธีแก้ปัญหา

1. เรียงลำดับคำตามความยาวจากน้อยไปมาก
2. ใช้ Hash Map (dp) เก็บความยาว chain สูงสุดที่ลงท้ายด้วยคำนั้นๆ
3. สำหรับแต่ละคำ ลองลบตัวอักษรทีละตัวเพื่อหา predecessor ที่เป็นไปได้
4. อัปเดต dp[word] = max(dp[predecessor] + 1)
5. ติดตามค่าสูงสุดตลอดการประมวลผล

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

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

class Solution {
public:
    static bool cmp(string s1, string s2) {
        return s1.size() < s2.size();
    }
    
    int longestStrChain(vector<string>& words) {
        unordered_map<string, int> dp;
        int n = words.size();
        sort(words.begin(), words.end(), cmp);
        int ret = 0;
        
        for(int i = 0; i < n; i++) {
            int best = 0;
            for(int j = 0; j < words[i].size(); j++) {
                string pred = words[i].substr(0, j) + words[i].substr(j + 1);
                best = max(best, dp[pred] + 1);
            }
            dp[words[i]] = best;
            ret = max(ret, dp[words[i]]);
        }
        return ret;
    }
};

int main() {
    vector<string> v = {"a","b","ba","bca","bda","bdca"};
    Solution ob;
    cout << ob.longestStrChain(v);
    return 0;
}

อินพุต

["a","b","ba","bca","bda","bdca"]

เอาต์พุต

4