【每日刷题】相隔为 1 的编辑距离

本文主要是介绍【每日刷题】相隔为 1 的编辑距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目地址

https://leetcode-cn.com/problems/one-edit-distance/

题目描述：相隔为1的编辑距离

给定两个字符串 s 和 t，判断他们的编辑距离是否为 1。

满足编辑距离等于 1 有三种可能的情形：

往 s 中插入一个字符得到 t ;
从 s 中删除一个字符得到 t ;
在 s 中替换一个字符得到 t .

示例：

例 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。

解答

这道题我想复杂了，我想的是动态规划。

实际上动态规划也能解决问题，但是时间复杂度达到了O(mn), 其中 m, n 为两个字符串的长度。因此会超时。

方法：首先比较两个字符串的长度，若相等，则证明只可能发生字符替换；若不相等，若需要返回 true, 则只能发生插入/删除。检测是否只发生一次改动。

class Solution {
public:bool isOneEditDistance(string s, string t) {int flag = 1;if( s.size() == t.size()){  //此时只有可能替换一个字符for( int i = 0; i < s.size(); i++)if( s[i] != t[i])flag--;return flag == 0;}//此时可能插入/删除；注，插入删除是相对而言的。int i = 0, j = 0;while( i < s.size() || j < t.size())if( i < s.size() && j < t.size() && s[i] == t[j])i++, j++;else if( i < s.size() && j < t.size()){flag--;if( s.size() > t.size())i++;else j++;}else if( i < s.size())i++, flag--;elsej++, flag--;return flag==0 && i == s.size() && j == t.size();}
};