给定两个字符串 s 和 t,判断他们的编辑距离是否为 1。
注意: 满足编辑距离等于 1 有三种可能的情形:
示例 1:
输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。
示例 2:
输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。
示例 3:
输入: s = "1203", t = "1213"
输出: true
解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/one-edit-distance 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
128 / 131 个通过测试用例,来了两个超级长的单词,时间复杂度太高
class Solution {
public:
bool isOneEditDistance(string s, string t) {
int m = s.size(), n = t.size(), i, j;
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for(i = 0; i <= m; i++)
dp[i][0] = i;
for(j = 0; j <= n; j++)
dp[0][j] = j;
for(i = 0; i < m; i++)
{
for(j = 0; j < n; j++)
{
if(s[i] == t[j])
dp[i+1][j+1] = dp[i][j];
else
{
dp[i+1][j+1] = min(dp[i+1][j],min(dp[i][j+1],dp[i][j]))+1;
}
}
}
return dp[m][n]==1;
}
};
class Solution {
public:
bool isOneEditDistance(string s, string t) {
int m = s.size(), n = t.size(), i = 0, j = 0, count = 0;
if(abs(m-n)>1) return false;
if(m==n)
{
while(i < m)
{
if(s[i] != t[i])
count++;
if(count > 1)
return false;
i++;
}
}
else//数量相差一个
{
count = 1;
if(m > n)
swap(s,t);// 让 s 短
bool founddiff = false;
for(i = 0; i < m; i++)
{
if(!founddiff && s[i] != t[i])//找到不相等的
founddiff = true;
if(founddiff && s[i] != t[i+1])//他跟t的下一个比较
count++;
if(count > 1)
return false;
}
}
return count==1;
}
};
4 ms 6.7 MB