数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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)，执行：
如果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
更新于：2020年11月18日
122 次浏览
广告