Leetcode P0161"One Edit Distance" 题解

博文中会简要介绍Leetcode P0161题目分析及解题思路。

“One Edit Distance”这道题是“最短编辑距离”的简化版，原题需要使用动态规划，而这道题由于只需要确定当前的编辑距离是不是恰好为1，解法上无需用动态规划，可以扫一遍得到结果。

Given two strings s and t, return true if they are both one edit distance apart, otherwise return false.

A string s is said to be one distance apart from a string t if you can:

Insert exactly one character into s to get t.

Delete exactly one character from s to get t.

Replace exactly one character of s with a different character to get t.

主要思路如下，

若两个字符串长度差超过1，或者两个字符串完全相等，则返回false。
遍历字符串s为，参考字符串t，若两者有不一致的地方，则有下述情况，
- 两者长度相等，则一定是replace操作。
- 字符串s更长，则是delete操作。
- 字符串t更长，则是insert操作。
若任何情况下，上述条件不满足，则其编辑距离都不会是1。

以下是Java的题解代码实现。

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int L1 = s.length(), L2 = t.length();
        if (Math.abs(L2-L1) > 1 || s.equals(t))
            return false;
        
        // 长度相差1时，任何一个字符串长度为0，两者之间编辑距离都是1
        if (L1 == 0 || L2 == 0)
            return true;
        
        int dist = 0, si = 0, ti = 0;
        while (si < L1) {
            if (ti == L2 || s.charAt(si) != t.charAt(ti)) {
                ++dist;
                if (dist > 1)
                    return false;
                
                // Insert
                if (L1 < L2) {
                    ++ti;
                }
                // Replace
                else if (L1 == L2) {
                    ++si;
                    ++ti;
                }
                // Delete
                else {
                    ++si;
                }
            }
            else {
                ++si;
                ++ti;
            }
        }
        
        return true;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        int L1 = s.length(), L2 = t.length();
        if (abs(L2-L1) > 1 || s == t)
            return false;
        
        if (L1 == 0 || L2 == 0)
            return true;
        
        int dist = 0, si = 0, ti = 0;
        while (si < L1) {
            if (ti == L2 || s[si] != t[ti]) {
                ++dist;
                if (dist > 1)
                    return false;
                
                if (L1 > L2)
                    ++si;
                else if (L1 < L2)
                    ++ti;
                else {
                    ++si;
                    ++ti;
                }
            }
            else {
                ++si;
                ++ti;
            }
        }
        
        return true;
    }
};

聖地亞歌

Leetcode P0161"One Edit Distance" 题解

Search

Table of Contents