Edit Distance

Edit Distance is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Edit Distance / Levenshtein Distance) subpattern.

Problem statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

- Insert a character

- Delete a character

- Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros" Output: 3 Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')

Example 2:

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')

Constraints:

- 0 <= word1.length, word2.length <= 500

- word1 and word2 consist of lowercase English letters.

Topics and companies

Topics: String, Dynamic Programming.

Reported in interviews at Amazon, Apple, Bloomberg, ByteDance, Facebook, Google, Microsoft, Palantir Technologies, Square.

How to practise Edit Distance on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n), where m = word1.length() and n = word2.length(). Each cell in the DP table is filled once. time and O(m * n) for the DP table of size (m+1) x (n+1). space.

Open Edit Distance in the code editor, or read the Edit Distance editorial for a worked solution with its approach and complexity analysis.

Where Edit Distance sits in the DSA pattern sheet

Problems related to Edit Distance

Other problems that use the same 2D Array (Edit Distance / Levenshtein Distance) and Dynamic Programming (DP) Patterns techniques:

Preparing this workspace.