資料結構
網路
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 次檢視
廣告