[Leetcode] One Edit Distance 编辑距离为一

lewinlee 发布于2019-08-14 12:48 / 1814人阅读

摘要：比较长度法复杂度时间空间思路虽然我们可以用的解法，看是否为，但中会超时。这里我们可以利用只有一个不同的特点在时间内完成。

One Edit Distance

Given two strings S and T, determine if they are both one edit distance apart.

比较长度法 复杂度

时间 O(N) 空间 O(1)

思路

虽然我们可以用Edit Distance的解法，看distance是否为1，但Leetcode中会超时。这里我们可以利用只有一个不同的特点在O(N)时间内完成。如果两个字符串只有一个编辑距离，则只有两种情况：

两个字符串一样长的时候，说明有一个替换操作，我们只要看对应位置是不是只有一个字符不一样就行了

一个字符串比另一个长1，说明有个增加或删除操作，我们就找到第一个对应位置不一样的那个字符，如果较长字符串在那个字符之后的部分和较短字符串那个字符及之后的部分是一样的，则符合要求

如果两个字符串长度差距大于1，肯定不对

代码

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length(), n = t.length();
        if(m == n) return isOneModified(s, t);
        if(m - n == 1) return isOneDeleted(s, t);
        if(n - m == 1) return isOneDeleted(t, s);
        // 长度差距大于2直接返回false
        return false;
    }
    
    private boolean isOneModified(String s, String t){
        boolean modified = false;
        // 看是否只修改了一个字符
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != t.charAt(i)){
                if(modified) return false;
                modified = true;
            }
        }
        return modified;
    }
    
    public boolean isOneDeleted(String longer, String shorter){
        // 找到第一组不一样的字符，看后面是否一样
        for(int i = 0; i < shorter.length(); i++){
            if(longer.charAt(i) != shorter.charAt(i)){
                return longer.substring(i + 1).equals(shorter.substring(i));
            }
        }
        return true;
    }
}

GPU云服务器云服务器编辑距离 Distance LeetCode html鼠标为一只手

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64723.html

Leetcode[161] One Edit Distance

摘要：复杂度思路考虑如果两个字符串的长度，是肯定当两个字符串中有不同的字符出现的时候，说明之后的字符串一定要相等。的长度比较大的时候，说明的时候，才能保证距离为。 LeetCode[161] One Edit Distance Given two strings S and T, determine if they are both one edit distance apart. Stri...

周国辉 2019-08-14 15:58 评论0 收藏0
[Leetcode] Edit Distance 最小编辑距离

摘要：动态规划复杂度时间空间思路这是算法导论中经典的一道动态规划的题。 Edit Distance Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You h...

zhangke3016 2019-08-14 12:29 评论0 收藏0
[LintCode/LeetCode] Edit Distance

摘要：构造数组，是的，是的，是将位的转换成位的需要的步数。初始化和为到它们各自的距离，然后两次循环和即可。 Problem Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 s...

snowell 2019-08-14 15:29 评论0 收藏0
LeetCode[72] Edit Distance

摘要：复杂度思路考虑用二维来表示变换的情况。如果两个字符串中的字符相等，那么如果两个字符串中的字符不相等，那么考虑不同的情况表示的是，从字符串到的位置转换到字符串到的位置，所需要的最少步数。 LeetCode[72] Edit Distance Given two words word1 and word2, find the minimum number of steps require...

call_me_R 2019-08-14 15:00 评论0 收藏0
leetcode72. Edit Distance

摘要：题目要求输入两个字符串和，允许对进行插入，删除和替换的操作，计算出将转化为所需要的最少的操作数。其中存储的是转换为的最小步数。首先从边缘情况开始考虑。只要在此基础上再进行一次插入操作即可以完成转换。题目要求 Given two words word1 and word2, find the minimum number of steps required to convert wor...

venmos 2019-08-15 11:07 评论0 收藏0