C ++中的一个编辑距离
假设我们有两个字符串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），执行-
如果n与m相同，则-
当s从索引0到(i)的子字符串与t从索引0到(i-1)的子字符串相同时，返回true
当s的从索引0到(i)的子字符串与t的从索引0到(i)的子字符串相同时，返回true
如果s[i]不等于t[i]，则-
当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