Why Take The Challenge?
Leetcode is a platform to practice and improve your coding skills, targetting data structures, time and space complexity. It teaches you to translate problem statement into code. It is a great resource to prepare for technical interviews. It has a lot of interesting and helpful coding questions that can help you be better prepared for an interview. You can pass the technical interviews at elite tech companies like Facebook, Amazon, Apple, Netflix, and Google. LeetCode questions are often asked during interviews at these companies, some more than at others.
‘Think twice, code once’
Pre-requisites
- Understanding of atleast one programming language
- Basic knowledge of data structures
Edit Distance: Problem Definition
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.
You have the following 3 operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Examples:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
Approach
For every element, we have 3 options: insert delete replace. We check which of these gives minimum nymber of operations in the final result and work accordingly.
Solution
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
M, N = len(word1), len(word2)
if M * N == 0:
return M + N
dp = [[0] * (N + 1) for i in range(M + 1)]
for i in range(M + 1):
dp[i][0] = i
for i in range(N + 1):
dp[0][i] = i
for i in range(1, M + 1):
for j in range(1, N + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1]))
return dp[M][N]
while(!(succeed=try()));
Submission Stats
1146 / 1146 test cases passed.
Status: Accepted
Runtime: 212 ms
Memory Usage: 17.4 MB
My runtime beat 36.36 % of python3 submissions
If you are stuck at any point or have any doubts, drop a message here