मान लीजिए हमारे पास दो शब्द w1 और w2 हैं, हमें हटाए गए वर्णों का न्यूनतम ASCII योग खोजना है ताकि w1 और w2 समान हो जाएं, जहां प्रत्येक चरण में हम किसी भी स्ट्रिंग में एक वर्ण हटा सकते हैं। इसलिए यदि इनपुट "sea" और "eat" जैसा है, तो आउटपुट 231 होगा, क्योंकि हमें w1 से 's' हटाना होगा, यह "ea" हो जाएगा और w2 से "eat" से "t" हटाना होगा। फिर वे समान हो जाएंगे। "eat" से 't' हटाने पर योग में 116 जुड़ जाता है, और अंत में, दोनों स्ट्रिंग्स समान होती हैं और 115 + 116 = 231 इसे प्राप्त करने के लिए न्यूनतम संभव योग है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n := s1 का आकार, m := s2 का आकार
- स्ट्रिंग्स s1 और s2 से पहले एक खाली स्थान जोड़ें, फिर s1 और s2 को तदनुसार अपडेट करें
- (n + 1) x (m + 1) आकार की एक तालिका बनाएं
- i := 1 से m तक
- dp[0, i] := dp[0, i - 1] + s2[i]
- i := 1 से n तक
- dp[i, 0] := dp[i - 1, 0] + s1[i]
- i को 1 से n तक की रेंज में
- j को 1 से m तक की रेंज में
- यदि s1[i] = s2[j]
- dp[i, j] := dp[i - 1, j - 1]
- अन्यथा dp[i, j] = dp[i - 1, j] + 1 और dp[i, j - 1] + 1 का न्यूनतम
- यदि s1[i] = s2[j]
- j को 1 से m तक की रेंज में
- dp[n, m] लौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; class Solution { public: int minimumDeleteSum(string s1, string s2) { int n = s1.size(); int m = s2.size(); s1 = " " + s1; s2 = " " + s2; vector < vector <int> > dp(n + 1, vector <int>(m + 1)); for(int i = 1; i <= m; i++){ dp[0][i] = dp[0][i - 1] + s2[i]; } for(int i = 1; i <= n; i++){ dp[i][0] = dp[i - 1][0] + s1[i]; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(s1[i] == s2[j]){ dp[i][j] = dp[i - 1][j - 1]; } else{ dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]); } } } return dp[n][m]; } }; main(){ Solution ob; cout << (ob.minimumDeleteSum("sea", "eat")); }इनपुट
"sea" "eat"
आउटपुट
231