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.
|
|
Note:
The length of given words won’t exceed 500.
Characters in given words can only be lower-case letters.
题目大意
给定两个字符串,求至少删除多少个字符才能使两个字符串相等。
解题思路
动态规划
遍历字符串,判断当前值相同和值不同时最少删除字符数。
12345 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)}
代码
|
|