LeetCode - #161 相隔为 1 的编辑距离（会员题）

原创

Swift社区

发布于 2025-01-05 22:21:28

1530

文章被收录于专栏：Swift社区Swift社区

前言

本题为 LeetCode 的高级会员解锁题

我们社区陆续会将顾毅（Netflix 增长黑客，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新到 159 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。

不积跬步，无以至千里；不积小流，无以成江海，Swift社区伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。

难度水平：中等

1. 描述

给定两个字符串 s 和 t，如果它们的编辑距离为 1，则返回 true，否则返回 false。

字符串 s 和字符串 t 之间满足编辑距离等于 1 有三种可能的情形：

往 s 中插入 恰好一个 字符得到 t
从 s 中删除 恰好一个 字符得到 t
在 s 中用 一个不同的字符 替换 恰好一个 字符得到 t

2. 示例

示例 1

输入: s = "ab", t = "acb"
输出: true
解释: 可以将 'c' 插入字符串 s 来得到 t。

示例 2

输入: s = "cab", t = "ad"
输出: false
解释: 无法通过 1 步操作使 s 变为 t。

示例 3

输入: s = "1203", t = "1213"
输出: true
解释: 可以将字符串 s 中的 '0' 替换为 '1' 来得到 t。

约束条件：

0 <= s.length <= 10^4
0 <= t.length <= 10^4
s 和 t 由小写字母、大写字母和/或数字组成。

3. 答案

enum Edit {
    case insert
    case delete
    case replace
}

class OneEditDistance {
    func isOneEditDistance(_ s: String, _ t: String) -> Bool {
        guard s != t else { 
            return false 
        }
        var editType = Edit.insert
        
        if s.count == t.count { 
            editType = .replace
        } else if s.count - t.count == 1 {
            editType = .delete
        } else if t.count - s.count == 1 {
            editType = .insert
        } else {
            return false 
        }
        
        let arr = Array(s), brr = Array(t)
        var flag = false, aIdx = 0, bIdx = 0
        
        while aIdx < arr.count && bIdx < brr.count {
            
            if arr[aIdx] != brr[bIdx] {
                
                guard !flag else { 
                    return false 
                }
                
                flag = true
                
                switch editType {
                case .insert: 
                    bIdx += 1
                case .delete: 
                    aIdx += 1
                case .replace: 
                    aIdx += 1
                    bIdx += 1
                }
            } else {
                aIdx += 1
                bIdx += 1
            }
            
        }
        return true 
    }
}