面试题01.05.一次编辑
面试题01.05.一次编辑
题解
题目:给定两个字符串,只能进行一次[增加一个字符,删除一个字符,修改一个字符],问能否在一次编辑,或者,零次编辑后,两个字符串相等
思路:
1.对于零次的情况:两个字符串本来就相等 2.如果两个字符串长度差为2,至少需要两次,直接返回false即可 3.遍历短的字符串,依次判断字符,直到遇到不相等的情况 如果两个字符串长度相等:修改----》直接判断后半串字符串是否相等 如果两个字符串不相等:对于短字符串来说是插入,对于长字符串来说是删除 -----》 判断s1[i:] == s2[i+1:]
代码
func oneEditAway(s1 string, s2 string) bool { n, m := len(s1), len(s2) //s1 小 s2 大 if n > m { return oneEditAway(s2, s1) } if m-n > 1 { return false } if s1 == s2 { return true } for i := 0; i < len(s2); i++ { if s2[i] != s1[i] { if len(s1) == len(s2) { return s1[i+1:] == s2[i+1:] } return s1[i:] == s2[i+1:] } } return true }