मान लीजिए हमारे पास शब्दों की एक सूची है, यहाँ प्रत्येक शब्द में छोटे अक्षर हैं। तो एक शब्द शब्द 1 दूसरे शब्द शब्द 2 का पूर्ववर्ती है यदि और केवल अगर हम शब्द 1 में कहीं भी एक अक्षर जोड़ सकते हैं ताकि इसे शब्द 2 के बराबर बनाया जा सके। पूर्ववर्ती के उदाहरण के लिए, "एबीसी" "एबैक" का पूर्ववर्ती है। अब एक शब्द शृंखला शब्दों का एक क्रम है [word_1, word_2, ..., word_k] k>=1 के साथ, जहां word_1, word_2 का पूर्ववर्ती है, word_2, word_3 का पूर्ववर्ती है, और इसी तरह। हमें शब्दों की दी गई सूची से चुने गए शब्दों के साथ एक शब्द श्रृंखला की सबसे लंबी संभव लंबाई ढूंढनी है।
तो अगर इनपुट इस तरह है:["ए", "बी", "बीए", "बीसीए", "बीडीए", "बीडीसीए"], तो परिणाम 4 होगा, क्योंकि सबसे लंबी श्रृंखला में से एक होगी [" ए", "बीए", "बीडीए", "बीडीसीए"]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
नक्शा डीपी परिभाषित करें, एन:=शब्द सरणी का आकार
-
शब्द सरणी को लंबाई के आधार पर क्रमबद्ध करें
-
रिट:=0
-
मैं के लिए 0 tn n - 1 की सीमा में हूं
-
सर्वोत्तम:=0
-
j के लिए 0 से लेकर शब्द की लंबाई तक [i] - 1
-
शब्द :=(शब्दों का सबस्ट्रिंग [i] 0 से j -1 तक) संयोजित (शब्दों का प्रतिस्थापन [i] j + 1 से अंत तक)
-
सर्वोत्तम:=अधिकतम सर्वोत्तम, डीपी [शब्द] + 1
-
-
डीपी [शब्द [i]]:=सर्वोत्तम
-
ret :=अधिकतम (ret, dp[words[i]])
-
-
वापसी रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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;
}
};
main(){
vector<string> v = {"a","b","ba","bca","bda","bdca"};
Solution ob;
cout << (ob.longestStrChain(v));
} इनपुट
["a","b","ba","bca","bda","bdca"]
आउटपुट
4