编辑距离为一

[编程题]编辑距离为一

热度指数：1177 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串 s 和 t ，如果两个字符串的编辑距离是 1 则输出 true 否则输出 false。

字符串 s 和字符串 t 的编辑距离是 1 时有三种情形。

从 s 中删除一个字符得到 t

往 s 中添加一个字符得到 t

在 s 中修改任意一个字符得到 t

数据范围：两个字符串的长度满足 $1 \le n \le 10^5 \$ ，字符串中仅包含小写英文字母

示例1

输入

"nowcoder","nawcoder"

输出

true

示例2

输入

"nowcoder","nawcader"

输出

false

算法知识视频讲解

牛客318321373号

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param t string字符串 
     * @return bool布尔型
     */
    bool editdistance(string s, string t) {
        // write code here
        if(s.length() == t.length() + 1){
            for(int i=0; i<t.length(); i++){
                if(s[i] != t[i]){
                    s.erase(s.begin()+i);
                    return s == t;
                }
            }
            return true;
        }
        if(s.length() == t.length() - 1){
            for(int i=0; i<s.length(); i++){
                if(s[i] != t[i]){
                    t.erase(t.begin()+i);
                    return s == t;
                }
            }
            return true;
        }
        if(s.length() == t.length()){
            if(s == t){
                return false;
            }
            for(int i=0; i<s.length(); i++){
                if(s[i] != t[i]){
                    s[i] = t[i];
                    return s == t;
                }
            }
        }
        return false;
    }
};

发表于 2022-11-14 22:48:16 回复(0)

Java

skwan

import java.util.*;


public class Solution {
    public boolean editdistance (String s, String t) {
        int lenS = s.length();
        int lenT = t.length();
        int dif = Math.abs(lenS - lenT);
        if (dif > 1) {
            return false;
        }
        if (lenS > lenT) {
            return editdistance(t, s);
        }
        // lenS <= lenT
        for (int i = 0; i < s.length(); i++) {
            // 如果两个字符不等
            if (s.charAt(i) != t.charAt(i)) {
                // 如果长度不等
                if (dif == 1) {
                    return s.substring(i).equals(t.substring(i + 1));
                } else {
                    return s.substring(i + 1).equals(t.substring(i + 1));
                }
            }
        }

        return dif == 1;
    }
}

发表于 2022-07-17 21:01:09 回复(0)

子沐728592488

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @param t string字符串
* @return bool布尔型
*
* C语言声明定义全局变量请加上static，防止重复定义
*/
bool editdistance(char* s, char* t ) {
// write code here
if ((s == NULL) || (t == NULL)) {
return false;
}

while ((*s != '\0') || (*t != '\0')) {
if (s[0] != t[0]) {
if ((strcmp(s + 1, t + 1) == 0) ||
(strcmp(s + 1, t) == 0) ||
(strcmp(s, t + 1) == 0)) {
return true;
} else {
return false;
}
}
s++;
t++;
}
return false;
}

发表于 2022-07-10 13:25:03 回复(0)

C++

牛客487629784号

    bool editdistance(string s, string t) {
        // write code here
        int lens=s.size();
        int lent=t.size();
        if(abs(lens-lent)>1)
        {
            return false;
        }
        if(lens==lent)//长度相同，只能修改一个字符
        {
            int cnt=0;
            for(int i=0;i<lens;i++)
            {
                if(s[i]!=t[i])
                {
                    cnt++;
                }
                if(cnt>1)
                {
                    return false;
                }
            }
            if(cnt==0)//完全相等，编辑距离为0
            {
                return false;
            }
        }
        else //长度短的添加一个字符
        {   
            if(lens<lent)
            {
                int cnt=0;
                for(int i=0;i<lens;i++)
                {
                    if(cnt==0)
                    {
                        if(s[i]!=t[i])
                        {
                            cnt++;
                            i--;
                        }
                    }
                    else
                    {
                        if(s[i]!=t[i+1])
                        {
                            return false;
                        }
                    }
                }
            }
            else
            {
                int cnt=0;
                for(int i=0;i<lent;i++)
                {
                    if(cnt==0)
                    {
                        if(s[i]!=t[i])
                        {
                            cnt++;
                            i--;
                        }
                    }
                    else
                    {
                        if(s[i+1]!=t[i])
                        {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

发表于 2022-07-01 14:29:47 回复(0)