Giả sử ta có một danh sách các từ, mỗi từ chỉ chứa chữ cái thường. Từ word1 là tiền tố của word2 nếu và chỉ nếu ta có thể thêm đúng một chữ cái vào bất kỳ vị trí nào của word1 để được word2. Ví dụ: "abc" là tiền tố của "abac". Một chuỗi từ là dãy [word_1, word_2, ..., word_k] với k ≥ 1, trong đó word_1 là tiền tố của word_2, word_2 là tiền tố của word_3, v.v. Ta cần tìm độ dài lớn nhất của chuỗi từ có thể tạo ra từ danh sách cho trước.
Ví dụ: đầu vào ["a","b","ba","bca","bda","bdca"], kết quả là 4, vì một trong các chuỗi dài nhất là ["a", "ba", "bda", "bdca"].
Giải pháp:
Định nghĩa map dp, n := kích thước mảng words
Sắp xếp mảng words theo độ dài tăng dần
ret := 0
Với i từ 0 đến n - 1:
best := 0
Với j từ 0 đến độ dài words[i] - 1:
word := words[i] bỏ ký tự tại vị trí j
best := max(best, dp[word] + 1)
dp[words[i]] := best
ret := max(ret, dp[words[i]])Trả về ret
Ví dụ
#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 word = words[i].substr(0, j) + words[i].substr(j + 1); best = max(best, dp[word] + 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)); }Đầu vào
["a","b","ba","bca","bda","bdca"]
Đầu ra
4