C++ 中的一次编辑距离
c++server side programmingprogramming
假设我们有两个字符串 s 和 t;我们需要检查它们是否都相差一次编辑距离。一次编辑距离有三种类型 −
在 s 中插入一个字符得到 t
从 s 中删除一个字符得到 t
替换 s 中的一个字符得到 t
因此，如果输入为 s = "ab", t = "acb"，则输出为 True
为了解决这个问题，我们将遵循以下步骤 −
n := s 的大小，m := t 的大小
如果 n < m，则 −
返回 isOneEditDistance(t, s)
初始化 i := 0，当 i < 时m，更新(将 i 加 1)，执行 −
如果 s[i] 不等于 t[i]，则 −
如果 n 与 m 相同，则 −
当 s 从索引 0 到 (i) 的子字符串与 t 从索引 0 到 (i) 的子字符串相同时返回 true
当 s 从索引 0 到 (i) 的子字符串与 t 从索引 0 到 (i - 1) 的子字符串相同时返回 true
当 m + 1 与 n 相同时返回 true
示例
让我们看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isOneEditDistance(string s, string t) {
int n = s.size();
int m = t.size();
if (n < m) {
return isOneEditDistance(t, s);
}
for (int i = 0; i < m; i++) {
if (s[i] != t[i]) {
if (n == m) {
return s.substr(i + 1) == t.substr(i + 1);
}
return s.substr(i + 1) == t.substr(i);
}
}
return m + 1 == n;
}
};
main(){
Solution ob;
cout << (ob.isOneEditDistance("ab", "acb"));
}
输入
s = "ab", t = "acb"
输出
1
