<p>Given two strings <code>word1</code> and <code>word2</code>, return <em>the minimum number of <strong>steps</strong> required to make</em> <code>word1</code> <em>and</em> <code>word2</code> <em>the same</em>.</p>

<p>In one <strong>step</strong>, you can delete exactly one character in either string.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> word1 = &quot;sea&quot;, word2 = &quot;eat&quot;
<strong>Output:</strong> 2
<strong>Explanation:</strong> You need one step to make &quot;sea&quot; to &quot;ea&quot; and another step to make &quot;eat&quot; to &quot;ea&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> word1 = &quot;leetcode&quot;, word2 = &quot;etco&quot;
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= word1.length, word2.length &lt;= 500</code></li>
	<li><code>word1</code> and <code>word2</code> consist of only lowercase English letters.</li>
</ul>

class Solution:
    def minDistance(self, A: str, B: str) -> int:
        source = (0, 0)
        target = (len(A), len(B))
        
        dist = defaultdict(lambda: inf, {source: 0})
        queue = deque((source,))
        
        def neighbors(i, j):
            if i == len(A):
                yield 1, (i, j + 1)
            elif j == len(B):
                yield 1, (i + 1, j)
            elif A[i] == B[j]:
                yield 0, (i + 1, j + 1)
            else:
                yield 1, (i, j + 1)
                yield 1, (i + 1, j)
        
        while queue:
            node = queue.popleft()
            if node == target:
                return dist[node]
            
            for weight, nei in neighbors(*node):
                ndist = dist[node] + weight
                if ndist < dist[nei]:
                    dist[nei] = ndist
                    queue.appendleft(nei) if weight == 0 else queue.append(nei)
                    
        return 0
16968