C++ में लॉन्गेस्ट स्ट्रिंग चेन (Longest String Chain)

मान लीजिए हमारे पास शब्दों की एक सूची है, जहां प्रत्येक शब्द लोअरकेस अक्षरों से बना है। एक शब्द word1 दूसरे शब्द word2 का पूर्ववर्ती (predecessor) होता है यदि और केवल यदि हम word1 में कहीं भी ठीक एक अक्षर जोड़कर इसे word2 के बराबर बना सकते हैं। उदाहरण के लिए, "abc", "abac" का पूर्ववर्ती है।

एक शब्द श्रृंखला (word chain) शब्दों का एक क्रम [word_1, word_2, ..., word_k] होता है जहां k ≥ 1, और word_1, word_2 का पूर्ववर्ती है, word_2, word_3 का पूर्ववर्ती है, इत्यादि। हमें दी गई शब्द सूची से चुने गए शब्दों की सबसे लंबी संभव शब्द श्रृंखला की लंबाई खोजनी है।

उदाहरण के लिए, यदि इनपुट ["a","b","ba","bca","bda","bdca"] है, तो परिणाम 4 होगा, क्योंकि सबसे लंबी श्रृंखलाओं में से एक ["a", "ba", "bda", "bdca"] है।

समाधान दृष्टिकोण

1. एक मैप dp परिभाषित करें, n := शब्द ऐरे का आकार

2. शब्द ऐरे को लंबाई के आधार पर सॉर्ट करें

3. ret := 0 सेट करें

4. प्रत्येक शब्द के लिए, उसके सभी संभावित पूर्ववर्ती बनाकर dp में खोजें और सर्वोत्तम श्रृंखला लंबाई अपडेट करें

5. अंत में ret लौटाएं

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 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)); 
    return 0; 
}

इनपुट

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

आउटपुट

4