समस्या विवरण
मान लीजिए हमारे पास दो स्ट्रिंग्स S और T हैं। हमें ऑपरेशन्स का सबसे छोटा अनुक्रम ढूंढना है जो S को T में बदलता है। यहां ऑपरेशन्स मूल रूप से या तो एक कैरेक्टर को हटाना या डालना है।
उदाहरण के लिए, यदि इनपुट है S = "xxxy", T = "xxyy", तो आउटपुट ["x", "x", "-x", "y", "+y"] होगा, इसका मतलब है पहले दो x रखें, फिर तीसरा x हटाएं, फिर y रखें फिर एक नया y जोड़ें।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम एडिट डिस्टेंस डायनामिक प्रोग्रामिंग का उपयोग करेंगे:
- आकार 505×505 का एक टेबल dp बनाएं
- एक फंक्शन help() परिभाषित करें जो i, j, S, T लेता है
- यदि i == S का आकार और j == T का आकार, तो dp[i][j] = 0 वापस करें
- यदि i == S का आकार, तो dp[i][j] = 1 + help(i, j+1, S, T) वापस करें
- यदि j == T का आकार, तो dp[i][j] = 1 + help(i+1, j, S, T) वापस करें
- यदि dp[i][j] != -1, तो dp[i][j] वापस करें
- dontDo := 1e5, del := 0, insert := 0
- यदि S[i] == T[j], तो dontDo := help(i+1, j+1, S, T)
- del := 1 + help(i+1, j, S, T)
- insert := 1 + help(i, j+1, S, T)
- minVal := min({dontDo, del, insert})
- dp[i][j] = minVal वापस करें
- एक फंक्शन getPath() परिभाषित करें जो i, j, S, T, curr, ret ऐरे लेता है
- यदि curr == 0 और i == S का आकार और j == T का आकार, तो वापस करें
- यदि i < S का आकार और j < T का आकार और S[i] == T[j] और dp[i+1][j+1] == curr:
- string(1, S[i]) को ret के अंत में डालें
- getPath(i+1, j+1, S, T, curr, ret)
- अन्यथा जब dp[i+1][j] + 1 == curr:
- "-" + string(1, S[i]) को ret के अंत में डालें
- getPath(i+1, j, S, T, curr-1, ret)
- अन्यथा:
- "+" + string(1, T[j]) को ret के अंत में डालें
- getPath(i, j+1, S, T, curr-1, ret)
- मुख्य विधि से:
- dp को -1 से भरें
- एक ऐरे ret परिभाषित करें
- x := help(0, 0, S, T)
- getPath(0, 0, S, T, x, ret)
- ret वापस करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ", ";
}
cout << "]" << endl;
}
int dp[505][505];
class Solution {
public:
int help(int i, int j, string& S, string& T) {
if (i == S.size() && j == T.size()) return dp[i][j] = 0;
if (i == S.size()) return dp[i][j] = 1 + help(i, j + 1, S, T);
if (j == T.size()) return dp[i][j] = 1 + help(i + 1, j, S, T);
if (dp[i][j] != -1) return dp[i][j];
int dontDo = 1e5;
int del = 0;
int insert = 0;
if (S[i] == T[j]) dontDo = help(i + 1, j + 1, S, T);
del = 1 + help(i + 1, j, S, T);
insert = 1 + help(i, j + 1, S, T);
int minVal = min({dontDo, del, insert});
return dp[i][j] = minVal;
}
void getPath(int i, int j, string& S, string& T, int curr, vector<string>& ret) {
if (curr == 0 && i == S.size() && j == T.size()) return;
if (i < S.size() && j < T.size() && S[i] == T[j] && dp[i + 1][j + 1] == curr) {
ret.push_back(string(1, S[i]));
getPath(i + 1, j + 1, S, T, curr, ret);
} else if (dp[i + 1][j] + 1 == curr) {
ret.push_back("-" + string(1, S[i]));
getPath(i + 1, j, S, T, curr - 1, ret);
} else {
ret.push_back("+" + string(1, T[j]));
getPath(i, j + 1, S, T, curr - 1, ret);
}
}
vector<string> solve(string S, string T) {
memset(dp, -1, sizeof dp);
vector<string> ret;
int x = help(0, 0, S, T);
getPath(0, 0, S, T, x, ret);
return ret;
}
};
vector<string> solve(string source, string target) {
return (new Solution())->solve(source, target);
}
int main() {
string S = "xxxy", T = "xxyy";
print_vector(solve(S, T));
}
इनपुट
"xxxy", "xxyy"
आउटपुट
[x, x, -x, y, +y, ]