数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序：将一个字符串转换为另一个字符串的操作
假设我们有两个字符串 S 和 T。我们需要找到将 S 转换为 T 的最短操作序列。这里的操作基本上是删除或插入一个字符。
因此，如果输入类似于 S = "xxxy" T = "xxyy"，则输出将是 ["x", "x", "-x", "y", "+y"]，这意味着放置前两个 x，然后删除第三个 x，然后放置 y，然后添加一个新的 y。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个大小为 505 x 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，则：
- 在 ret 的末尾插入字符串(1, S[i])
- getPath(i + 1, j + 1, S, T, curr, ret)
- 否则，当 dp[i + 1, j] + 1 等于 curr 时，则：
- 在 ret 的末尾插入 ("-" 连接字符串(1, S[i]))
- getPath(i + 1, j, S, T, curr - 1, ret)
- 否则
- 在 ret 的末尾插入 ("+" 连接字符串(1, T[j]))
- getPath(i, j + 1, S, T, curr - 1, ret)
- 在主方法中执行以下操作：
- 用 -1 填充 dp
- 定义一个数组 ret
- x := help(0, 0, S, T)
- getPath(0, 0, S, T, x, ret)
- 返回 ret
示例 (C++)
让我们看以下实现以更好地理解：
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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);
}
main(){
string S = "xxxy", T = "xxyy";
print_vector(solve(S, T));
}输入
"xxxy", "xxyy"
输出
[x, x, -x, y, +y, ]
更新于：2020-12-12
167 次查看
广告