前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 161. 相隔为 1 的编辑距离(DP/遍历)

LeetCode 161. 相隔为 1 的编辑距离(DP/遍历)

作者头像
Michael阿明
发布2020-07-13 14:52:27
8280
发布2020-07-13 14:52:27
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

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

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

  • 往 s 中插入一个字符得到 t
  • 从 s 中删除一个字符得到 t
  • 在 s 中替换一个字符得到 t
代码语言:javascript
复制
示例 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

2.1 DP超时

128 / 131 个通过测试用例,来了两个超级长的单词,时间复杂度太高

代码语言:javascript
复制
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;
    }
};

2.2 一次遍历

代码语言:javascript
复制
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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/07/07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
    • 2.1 DP超时
      • 2.2 一次遍历
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档