:orphan:

Edit Distance
=============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/edit-distance/

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.

.. highlight:: python

Pattern
-------
String, Dynamic Programming

Approaches
----------

.. tab-set::

    .. tab-item:: Dynamic Programming

        **Code**

        .. literalinclude:: ../problems/medium/edit-distance/edit_distance__dynamic_programming.py
            :language: python
            :lines: 10-

        **Test**

        >>> from edit_distance__dynamic_programming import minDistance
        >>> minDistance("horse", "ros")
        3
        >>> minDistance("intention", "execution")
        5

        .. autofunction:: edit_distance__dynamic_programming.minDistance