엔지니어 게시판
LeetCode 솔루션 분류

[6/14] 583. Delete Operation for Two Strings

• mingki 작성
• 작성일

• 140 조회
• 2 댓글

본문

Medium

Given two strings `word1` and `word2`, return the minimum number of steps required to make `word1` and `word2` the same.

In one step, you can delete exactly one character in either string.

Example 1:

```Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
```

Example 2:

```Input: word1 = "leetcode", word2 = "etco"
Output: 4
```

Constraints:

• `1 <= word1.length, word2.length <= 500`
• `word1` and `word2` consist of only lowercase English letters.

댓글 2

학부유학생님의 댓글

• 학부유학생
• 작성일
Runtime: 392 ms, faster than 51.22% of Python3 online submissions for Delete Operation for Two Strings.
Memory Usage: 13.9 MB, less than 92.06% of Python3 online submissions for Delete Operation for Two Strings.
``````class Solution:
def minDistance(self, word1: str, word2: str) -> int:
if len(word1) < len(word2):
word1, word2 = word2, word1

long, short = len(word1), len(word2)

prev = [i for i in range(long+1)]

for idx, char in enumerate(word2):
curr = [0]*(long+1)
curr[0] = idx + 1
for i in range(1,long+1):
if char == word1[i-1]:
curr[i] = prev[i-1]
else:
curr[i] = 1+min(prev[i], curr[i-1])

prev = curr

return curr[-1]``````

Coffee님의 댓글

• Coffee
• 작성일
``````class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length() +1][word2.length()+1];

for(int i=0; i<=word1.length(); i++){
for(int j=0; j<=word2.length(); j++){
if(i == 0 || j == 0){
continue;
}

if(word1.charAt(i-1) == word2.charAt(j-1)){
dp[i][j] = 1 + dp[i-1][j-1];
}else{
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}

return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
}

}``````
전체 127 / 1 페이지

새댓글

• 등록자 JakeMinSVK 등록일 18:25
• 등록자 JakeMinSVK 등록일 18:24
• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}