首页 > 试题广场 >

编辑距离为一

[编程题]编辑距离为一
  • 热度指数:1177 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串 s 和 t ,如果两个字符串的编辑距离是 1 则输出 true 否则输出 false。
字符串 s 和字符串 t 的编辑距离是 1 时有三种情形。
从 s 中删除一个字符得到 t
往 s 中添加一个字符得到 t
在 s 中修改任意一个字符得到 t

数据范围:两个字符串的长度满足 ,字符串中仅包含小写英文字母
示例1

输入

"nowcoder","nawcoder"

输出

true
示例2

输入

"nowcoder","nawcader"

输出

false
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)