मान लीजिए हमारे पास दो शब्द w1 और w2 हैं, हमें w1 और w2 को समान बनाने के लिए आवश्यक न्यूनतम चरणों की संख्या ढूंढनी है, जहां प्रत्येक चरण में हम किसी भी स्ट्रिंग में एक वर्ण हटा सकते हैं। इसलिए यदि इनपुट "sea" और "eat" जैसा है, तो आउटपुट 2 होगा, क्योंकि हमें w1 से 's' हटाना होगा, यह "ea" हो जाएगा और w2 से "eat" से "t" हटाना होगा। फिर वे समान हो जाएंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे
- n := s1 का आकार, m := s2 का आकार
- स्ट्रिंग्स s1 और s2 से पहले एक खाली स्थान जोड़ें, फिर s1 और s2 को तदनुसार अपडेट करें
- (n + 1) x (m + 1) आकार की एक तालिका बनाएं
- i := 1 से m तक
- dp[0, i] := dp[0, i - 1] + 1
- i := 1 से n तक
- dp[i, 0] := dp[i - 1, 0] + 1
- 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 minDistance(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] + 1; } for(int i = 1; i <= n; i++){ dp[i][0] = dp[i - 1][0] + 1; } 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] + 1, dp[i][j - 1] + 1); } } } return dp[n][m]; } }; main(){ Solution ob; vector<int> v = {1,1,1}; cout << (ob.minDistance("sea", "eat")); }इनपुट
"sea" "eat"
आउटपुट
2
