583. Delete Operation for Two Strings

发表于 | 分类于 | |

583. Delete Operation for Two Strings

题目描述

Given two words word1 and word2, find the minimum number of steps required to make word1 and word2 the same, where in each step you can delete one character in either string.

1
2
3
4
5
Example 1:
Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and
another step to make "eat" to "ea".

Note:
The length of given words won’t exceed 500.
Characters in given words can only be lower-case letters.

题目大意

给定两个字符串，求至少删除多少个字符才能使两个字符串相等。

解题思路

动态规划
遍历字符串，判断当前值相同和值不同时最少删除字符数。

1
2
3
4
5
if chars1[i - 1] == chars2[j - 1] {
    dp[i][j] = dp[i - 1][j - 1]
}else {
    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
}

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    func minDistance(_ word1: String, _ word2: String) -> Int {
        
        guard !word1.isEmpty && !word2.isEmpty else {
            return word1.isEmpty ? word2.count : word1.count
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: word2.count + 1), count: word1.count + 1)
        
        let chars1 = Array(word1)
        let chars2 = Array(word2)
        let c1 = word1.count
        let c2 = word2.count
        
        for i in 0...c1 { dp[i][0] = i }
        for i in 0...c2 { dp[0][i] = i }
        
        
        for i in 1...c1 {
            for j in 1...c2 {
                if chars1[i - 1] == chars2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1]
                }else {
                    dp[i][j] = min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
                }
            }
        }
        return dp[c1][c2]
    }
}
0%