golang刷leetcode技巧之如何实现一次编辑

一、问题描述

给定两个字符串s和t，判断它们是否只需要进行一次编辑（插入、删除或替换一个字符）就可以相等。例如，字符串"pale"和"ple"属于只需要进行一次编辑就可以相等的情况。

二、解决思路

为了判断两个字符串是否只需要进行一次编辑就可以相等，需要考虑以下几种情况：

1. 字符串s与字符串t的长度差大于1，直接返回false。

2. 字符串s与字符串t的长度差等于1，判断是否可以通过插入或删除一个字符来使得两个字符串相等。可以通过一次遍历字符串s和字符串t，当遇到第一个不相同的字符时，分别判断删除s中该字符后的剩余字符串是否与t相同，或者在s中插入t中缺失的字符后是否与t相同。

3. 字符串s与字符串t的长度相等，判断是否可以通过替换一个字符使得两个字符串相等。可以通过一次遍历字符串s和字符串t，当遇到第一个不相同的字符时，判断删除该字符后的剩余字符串是否与t相同。

三、代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isOneEditDistance(s string, t string) bool {

    m, n := len(s), len(t)

    if abs(m-n) > 1 {

        return false

    }

    

    for i:=0; i
        if s[i] != t[i] {

            if m == n {

                return s[i+1:] == t[i+1:]

            } else if m < n {

                return s[i:] == t[i+1:]

            } else {

                return s[i+1:] == t[i:]

            }

        }

    }

    

    return abs(m-n) == 1

}



func abs(a int) int {

    if a < 0 {

        return -a

    }

    return a

}



func min(a, b int) int {

    if a < b {

        return a

    }

    return b

}

上述代码中的isOneEditDistance函数用于判断两个字符串s和t是否只需要进行一次编辑就可以相等。首先判断两个字符串的长度差，根据长度差的不同情况进行处理。接下来通过一次遍历字符串s和t，当遇到第一个不相同的字符时，根据长度差的情况判断是否可以通过插入、删除或替换一个字符使得两个字符串相等。