Day 9 - Word Ladder

January LeetCoding Challenge 2021 (33 Part Series)

1 Day1 – Check Array Formation Through Concatenation
2 Week 1 Bonus – Palindrome Permutation
… 29 more parts…
3 Day 2 Find a Corresponding Node of a Binary Tree in a Clone of That Tree
4 Day 3 – Beautiful Arrangement
5 Day 4 – Merge Two Sorted Lists
6 Day 5 – Remove Duplicates from Sorted List II
7 Day 6 – Kth Missing Positive Number
8 Day 7 – Longest Substring Without Repeating Characters
9 Day 8 – Check If Two String Arrays are Equivalent
10 Day 9 – Word Ladder
11 Day 10 – Create Sorted Array through Instructions
12 Day 11 – Merge Sorted Array
13 Day 12 – Add Two Numbers
14 Day 13 – Boats to Save People
15 Day 14 – Minimum Operations to Reduce X to Zero
16 Week 2 Bonus – Find Root of N-Ary Tree
17 Day 15 – Get Maximum in Generated Array
18 Day 16 – Kth Largest Element in an Array
19 Day 17 – Count Sorted Vowel Strings
20 Day 18 – Max Number of K-Sum Pairs
21 Week 3 Bonus – Nested List Weight Sum
22 Day 19 – Longest Palindromic Substring
23 Day 20 – Valid Parentheses
24 Day 21 – Find the Most Competitive Subsequence
25 Day 22 – Determine if Two Strings Are Close
26 Day 23 – Sort the Matrix Diagonally
27 Day 24 – Merge k Sorted Lists
28 Day 25 – Check If All 1’s Are at Least Length K Places Away
29 Day 28 – Smallest String With A Given Numeric Value
30 Day 27 – Concatenation of Consecutive Binary Numbers
31 Day 29 – Vertical Order Traversal of a Binary Tree
32 Day 30 – Minimize Deviation in Array
33 Day 31 – Next Permutation

The Problem

Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.

Each transformed word must exist in the word list.

Return 0 if there is no such transformation sequence.

Example 1:


Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Enter fullscreen mode Exit fullscreen mode

Example 2:


Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

Enter fullscreen mode Exit fullscreen mode

Constraints:

1 <= beginWord.length <= 100
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord, endWord, and wordList[i] consist of lowercase English letters.
beginWord != endWord
All the strings in wordList are unique.

My Tests


<span>import</span> <span>pytest</span>
<span>from</span> <span>.Day9</span> <span>import</span> <span>Solution</span>
<span>s</span> <span>=</span> <span>Solution</span><span>()</span>
<span>@</span><span>pytest</span><span>.</span><span>mark</span><span>.</span><span>parametrize</span><span>(</span>
    <span>"beginWord,endWord,wordList,expected"</span><span>,</span>
    <span>[</span>
        <span>(</span><span>"hit"</span><span>,</span> <span>"cog"</span><span>,</span> <span>[</span><span>"hot"</span><span>,</span> <span>"dot"</span><span>,</span> <span>"dog"</span><span>,</span> <span>"lot"</span><span>,</span> <span>"log"</span><span>,</span> <span>"cog"</span><span>],</span> <span>5</span><span>),</span>        
        <span>(</span><span>"hit"</span><span>,</span> <span>"cog"</span><span>,</span> <span>[</span><span>"hot"</span><span>,</span> <span>"dot"</span><span>,</span> <span>"dog"</span><span>,</span> <span>"lot"</span><span>,</span> <span>"log"</span><span>],</span> <span>0</span><span>),</span>
        <span>(</span><span>"count"</span><span>,</span> <span>"court"</span><span>,</span> <span>[</span><span>"mount"</span><span>,</span> <span>"point"</span><span>],</span> <span>0</span><span>),</span>
    <span>],</span>
<span>)</span>
<span>def</span> <span>test_ladder_length</span><span>(</span><span>beginWord</span><span>,</span> <span>endWord</span><span>,</span> <span>wordList</span><span>,</span> <span>expected</span><span>):</span>
    <span>assert</span> <span>s</span><span>.</span><span>ladderLength</span><span>(</span><span>beginWord</span><span>,</span> <span>endWord</span><span>,</span> <span>wordList</span><span>)</span> <span>==</span> <span>expected</span>
<span>import</span> <span>pytest</span>
<span>from</span> <span>.Day9</span> <span>import</span> <span>Solution</span>

<span>s</span> <span>=</span> <span>Solution</span><span>()</span>


<span>@</span><span>pytest</span><span>.</span><span>mark</span><span>.</span><span>parametrize</span><span>(</span>
    <span>"beginWord,endWord,wordList,expected"</span><span>,</span>
    <span>[</span>
        <span>(</span><span>"hit"</span><span>,</span> <span>"cog"</span><span>,</span> <span>[</span><span>"hot"</span><span>,</span> <span>"dot"</span><span>,</span> <span>"dog"</span><span>,</span> <span>"lot"</span><span>,</span> <span>"log"</span><span>,</span> <span>"cog"</span><span>],</span> <span>5</span><span>),</span>        
        <span>(</span><span>"hit"</span><span>,</span> <span>"cog"</span><span>,</span> <span>[</span><span>"hot"</span><span>,</span> <span>"dot"</span><span>,</span> <span>"dog"</span><span>,</span> <span>"lot"</span><span>,</span> <span>"log"</span><span>],</span> <span>0</span><span>),</span>
        <span>(</span><span>"count"</span><span>,</span> <span>"court"</span><span>,</span> <span>[</span><span>"mount"</span><span>,</span> <span>"point"</span><span>],</span> <span>0</span><span>),</span>
    <span>],</span>
<span>)</span>
<span>def</span> <span>test_ladder_length</span><span>(</span><span>beginWord</span><span>,</span> <span>endWord</span><span>,</span> <span>wordList</span><span>,</span> <span>expected</span><span>):</span>
    <span>assert</span> <span>s</span><span>.</span><span>ladderLength</span><span>(</span><span>beginWord</span><span>,</span> <span>endWord</span><span>,</span> <span>wordList</span><span>)</span> <span>==</span> <span>expected</span>
import pytest
from .Day9 import Solution

s = Solution()


@pytest.mark.parametrize(
    "beginWord,endWord,wordList,expected",
    [
        ("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"], 5),        
        ("hit", "cog", ["hot", "dot", "dog", "lot", "log"], 0),
        ("count", "court", ["mount", "point"], 0),
    ],
)
def test_ladder_length(beginWord, endWord, wordList, expected):
    assert s.ladderLength(beginWord, endWord, wordList) == expected

Enter fullscreen mode Exit fullscreen mode

My Solution


<span>from</span> <span>typing</span> <span>import</span> <span>List</span><span>,</span> <span>Dict</span>
<span>import</span> <span>collections</span>
<span>def</span> <span>getLadderLength</span><span>(</span>
    <span>queue</span><span>,</span>
    <span>visited</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>int</span><span>],</span>
    <span>otherVisited</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>int</span><span>],</span>
    <span>wordLength</span><span>:</span> <span>int</span><span>,</span>
    <span>combos</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>List</span><span>[</span><span>str</span><span>]],</span>
<span>):</span>
    <span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
        <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
        <span>if</span> <span>testWord</span> <span>in</span> <span>combos</span><span>:</span>
            <span>for</span> <span>w</span> <span>in</span> <span>combos</span><span>[</span><span>testWord</span><span>]:</span>
                <span>if</span> <span>w</span> <span>in</span> <span>otherVisited</span><span>:</span>
                    <span>return</span> <span>level</span> <span>+</span> <span>otherVisited</span><span>[</span><span>w</span><span>]</span>
                <span>if</span> <span>w</span> <span>not</span> <span>in</span> <span>visited</span><span>:</span>
                    <span>visited</span><span>[</span><span>w</span><span>]</span> <span>=</span> <span>level</span> <span>+</span> <span>1</span>
                    <span>queue</span><span>.</span><span>append</span><span>((</span><span>w</span><span>,</span> <span>level</span> <span>+</span> <span>1</span><span>))</span>
    <span>return</span> <span>0</span>
<span>def</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>],</span> <span>wordLength</span><span>:</span> <span>int</span><span>):</span>
    <span>combos</span> <span>=</span> <span>{}</span>
    <span>for</span> <span>word</span> <span>in</span> <span>wordList</span><span>:</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
            <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
            <span>if</span> <span>testWord</span> <span>not</span> <span>in</span> <span>combos</span><span>:</span>
                <span>combos</span><span>[</span><span>testWord</span><span>]</span> <span>=</span> <span>[]</span>
            <span>combos</span><span>[</span><span>testWord</span><span>].</span><span>append</span><span>(</span><span>word</span><span>)</span>
    <span>return</span> <span>combos</span>
<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>ladderLength</span><span>(</span><span>self</span><span>,</span> <span>beginWord</span><span>:</span> <span>str</span><span>,</span> <span>endWord</span><span>:</span> <span>str</span><span>,</span> <span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>])</span> <span>-></span> <span>int</span><span>:</span>
        <span>if</span> <span>endWord</span> <span>not</span> <span>in</span> <span>wordList</span><span>:</span>
            <span>return</span> <span>0</span>
        <span>wl</span> <span>=</span> <span>len</span><span>(</span><span>beginWord</span><span>)</span>
        <span>combos</span> <span>=</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>,</span> <span>wl</span><span>)</span>
        <span>qBegin</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>beginWord</span><span>,</span> <span>1</span><span>)])</span>
        <span>qEnd</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>endWord</span><span>,</span> <span>1</span><span>)])</span>
        <span>visitedBegin</span> <span>=</span> <span>{</span><span>beginWord</span><span>:</span> <span>1</span><span>}</span>
        <span>visitedEnd</span> <span>=</span> <span>{</span><span>endWord</span><span>:</span> <span>1</span><span>}</span>
        <span>ladderLength</span> <span>=</span> <span>0</span>
        <span>while</span> <span>qBegin</span> <span>and</span> <span>qEnd</span><span>:</span>
            <span>ladderLength</span> <span>=</span> <span>getLadderLength</span><span>(</span><span>qBegin</span><span>,</span> <span>visitedBegin</span><span>,</span> <span>visitedEnd</span><span>,</span> <span>wl</span><span>,</span> <span>combos</span><span>)</span>
            <span>if</span> <span>ladderLength</span> <span>></span> <span>0</span><span>:</span>
                <span>return</span> <span>ladderLength</span>
            <span>ladderLength</span> <span>=</span> <span>getLadderLength</span><span>(</span><span>qEnd</span><span>,</span> <span>visitedEnd</span><span>,</span> <span>visitedBegin</span><span>,</span> <span>wl</span><span>,</span> <span>combos</span><span>)</span>
            <span>if</span> <span>ladderLength</span> <span>></span> <span>0</span><span>:</span>
                <span>return</span> <span>ladderLength</span>
        <span>return</span> <span>0</span>
<span>from</span> <span>typing</span> <span>import</span> <span>List</span><span>,</span> <span>Dict</span>
<span>import</span> <span>collections</span>


<span>def</span> <span>getLadderLength</span><span>(</span>
    <span>queue</span><span>,</span>
    <span>visited</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>int</span><span>],</span>
    <span>otherVisited</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>int</span><span>],</span>
    <span>wordLength</span><span>:</span> <span>int</span><span>,</span>
    <span>combos</span><span>:</span> <span>Dict</span><span>[</span><span>str</span><span>,</span> <span>List</span><span>[</span><span>str</span><span>]],</span>
<span>):</span>
    <span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
        <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
        <span>if</span> <span>testWord</span> <span>in</span> <span>combos</span><span>:</span>
            <span>for</span> <span>w</span> <span>in</span> <span>combos</span><span>[</span><span>testWord</span><span>]:</span>
                <span>if</span> <span>w</span> <span>in</span> <span>otherVisited</span><span>:</span>
                    <span>return</span> <span>level</span> <span>+</span> <span>otherVisited</span><span>[</span><span>w</span><span>]</span>
                <span>if</span> <span>w</span> <span>not</span> <span>in</span> <span>visited</span><span>:</span>
                    <span>visited</span><span>[</span><span>w</span><span>]</span> <span>=</span> <span>level</span> <span>+</span> <span>1</span>
                    <span>queue</span><span>.</span><span>append</span><span>((</span><span>w</span><span>,</span> <span>level</span> <span>+</span> <span>1</span><span>))</span>
    <span>return</span> <span>0</span>


<span>def</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>],</span> <span>wordLength</span><span>:</span> <span>int</span><span>):</span>
    <span>combos</span> <span>=</span> <span>{}</span>
    <span>for</span> <span>word</span> <span>in</span> <span>wordList</span><span>:</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
            <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
            <span>if</span> <span>testWord</span> <span>not</span> <span>in</span> <span>combos</span><span>:</span>
                <span>combos</span><span>[</span><span>testWord</span><span>]</span> <span>=</span> <span>[]</span>
            <span>combos</span><span>[</span><span>testWord</span><span>].</span><span>append</span><span>(</span><span>word</span><span>)</span>
    <span>return</span> <span>combos</span>


<span>class</span> <span>Solution</span><span>:</span>
    <span>def</span> <span>ladderLength</span><span>(</span><span>self</span><span>,</span> <span>beginWord</span><span>:</span> <span>str</span><span>,</span> <span>endWord</span><span>:</span> <span>str</span><span>,</span> <span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>])</span> <span>-></span> <span>int</span><span>:</span>
        <span>if</span> <span>endWord</span> <span>not</span> <span>in</span> <span>wordList</span><span>:</span>
            <span>return</span> <span>0</span>
        <span>wl</span> <span>=</span> <span>len</span><span>(</span><span>beginWord</span><span>)</span>
        <span>combos</span> <span>=</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>,</span> <span>wl</span><span>)</span>

        <span>qBegin</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>beginWord</span><span>,</span> <span>1</span><span>)])</span>
        <span>qEnd</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>endWord</span><span>,</span> <span>1</span><span>)])</span>

        <span>visitedBegin</span> <span>=</span> <span>{</span><span>beginWord</span><span>:</span> <span>1</span><span>}</span>
        <span>visitedEnd</span> <span>=</span> <span>{</span><span>endWord</span><span>:</span> <span>1</span><span>}</span>
        <span>ladderLength</span> <span>=</span> <span>0</span>

        <span>while</span> <span>qBegin</span> <span>and</span> <span>qEnd</span><span>:</span>
            <span>ladderLength</span> <span>=</span> <span>getLadderLength</span><span>(</span><span>qBegin</span><span>,</span> <span>visitedBegin</span><span>,</span> <span>visitedEnd</span><span>,</span> <span>wl</span><span>,</span> <span>combos</span><span>)</span>
            <span>if</span> <span>ladderLength</span> <span>></span> <span>0</span><span>:</span>
                <span>return</span> <span>ladderLength</span>
            <span>ladderLength</span> <span>=</span> <span>getLadderLength</span><span>(</span><span>qEnd</span><span>,</span> <span>visitedEnd</span><span>,</span> <span>visitedBegin</span><span>,</span> <span>wl</span><span>,</span> <span>combos</span><span>)</span>
            <span>if</span> <span>ladderLength</span> <span>></span> <span>0</span><span>:</span>
                <span>return</span> <span>ladderLength</span>

        <span>return</span> <span>0</span>
from typing import List, Dict
import collections


def getLadderLength(
    queue,
    visited: Dict[str, int],
    otherVisited: Dict[str, int],
    wordLength: int,
    combos: Dict[str, List[str]],
):
    word, level = queue.popleft()
    for i in range(wordLength):
        testWord = word[:i] + "*" + word[i + 1 :]
        if testWord in combos:
            for w in combos[testWord]:
                if w in otherVisited:
                    return level + otherVisited[w]
                if w not in visited:
                    visited[w] = level + 1
                    queue.append((w, level + 1))
    return 0


def preProcessNeighbors(wordList: List[str], wordLength: int):
    combos = {}
    for word in wordList:
        for i in range(wordLength):
            testWord = word[:i] + "*" + word[i + 1 :]
            if testWord not in combos:
                combos[testWord] = []
            combos[testWord].append(word)
    return combos


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0
        wl = len(beginWord)
        combos = preProcessNeighbors(wordList, wl)

        qBegin = collections.deque([(beginWord, 1)])
        qEnd = collections.deque([(endWord, 1)])

        visitedBegin = {beginWord: 1}
        visitedEnd = {endWord: 1}
        ladderLength = 0

        while qBegin and qEnd:
            ladderLength = getLadderLength(qBegin, visitedBegin, visitedEnd, wl, combos)
            if ladderLength > 0:
                return ladderLength
            ladderLength = getLadderLength(qEnd, visitedEnd, visitedBegin, wl, combos)
            if ladderLength > 0:
                return ladderLength

        return 0

Enter fullscreen mode Exit fullscreen mode

Analysis

My Commentary

After doing this one I am currently experiencing a high level of hate for coding problems. I had actually solved a problem similar to this some time ago so I even had the benefit of working from memory in some aspects but it still drove me a little crazy.

Looking at the problem we know we need to create a path of words going from the beginWord to the endWord. Looking at the example it might be intuitive at first to imagine iterating over the list, check which words differ by one letter, count the transformations along the way. That quickly breaks down once you change the example to be a little more complex. My next intuition was to maybe have a map of the various paths and return the shortest. That would get way too messy though. What would you use as a key? Do you have to access every list too often?

If we need a path and we need to track path length then the data structure we need is clearly a graph. Each node is a word with the level the node is on the path between beginning and end. Each neighbour of a node must contain another word that differs by only one letter. That way we adhere to the requirement that each transformation changes only one letter.

The first thing we do is check if the endWord is in the list at all and return 0 if not.

Then we must preprocess the graph.


<span>def</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>],</span> <span>wordLength</span><span>:</span> <span>int</span><span>):</span>
    <span>combos</span> <span>=</span> <span>{}</span>
    <span>for</span> <span>word</span> <span>in</span> <span>wordList</span><span>:</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
            <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
            <span>if</span> <span>testWord</span> <span>not</span> <span>in</span> <span>combos</span><span>:</span>
                <span>combos</span><span>[</span><span>testWord</span><span>]</span> <span>=</span> <span>[]</span>
            <span>combos</span><span>[</span><span>testWord</span><span>].</span><span>append</span><span>(</span><span>word</span><span>)</span>
    <span>return</span> <span>combos</span>
<span>def</span> <span>preProcessNeighbors</span><span>(</span><span>wordList</span><span>:</span> <span>List</span><span>[</span><span>str</span><span>],</span> <span>wordLength</span><span>:</span> <span>int</span><span>):</span>
    <span>combos</span> <span>=</span> <span>{}</span>
    <span>for</span> <span>word</span> <span>in</span> <span>wordList</span><span>:</span>
        <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
            <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
            <span>if</span> <span>testWord</span> <span>not</span> <span>in</span> <span>combos</span><span>:</span>
                <span>combos</span><span>[</span><span>testWord</span><span>]</span> <span>=</span> <span>[]</span>
            <span>combos</span><span>[</span><span>testWord</span><span>].</span><span>append</span><span>(</span><span>word</span><span>)</span>
    <span>return</span> <span>combos</span>
def preProcessNeighbors(wordList: List[str], wordLength: int):
    combos = {}
    for word in wordList:
        for i in range(wordLength):
            testWord = word[:i] + "*" + word[i + 1 :]
            if testWord not in combos:
                combos[testWord] = []
            combos[testWord].append(word)
    return combos

Enter fullscreen mode Exit fullscreen mode

wordLength is pretty much a constant based on the constraints:

endWord.length == beginWord.length
wordList[i].length == beginWord.length

We iterate over every word in our word list. Then we generate versions of the word replacing each letter with a *. So for example, say the word is can. We generate 3 words: *an, c*n, ca*. We are going to use these as keys and create a data structure that looks like this:


<span>{</span><span> </span><span>"*an"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>],</span><span> </span><span>"c*n"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>],</span><span> </span><span>"ca*"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>]</span><span> </span><span>}</span><span> </span>
<span>{</span><span> </span><span>"*an"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>],</span><span> </span><span>"c*n"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>],</span><span> </span><span>"ca*"</span><span>:</span><span> </span><span>[</span><span>"can"</span><span>]</span><span> </span><span>}</span><span> </span>
{ "*an": ["can"], "c*n": ["can"], "ca*": ["can"] }

Enter fullscreen mode Exit fullscreen mode

What use is this?

Imagine we have a word list like this:


["hot", "dot", "dog", "cog"]
["hot", "dot", "dog", "cog"]
["hot", "dot", "dog", "cog"]

Enter fullscreen mode Exit fullscreen mode

If we use the preprocessing above we will end up with a data structure like this:


<span>{</span><span> </span><span>"*ot"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>,</span><span> </span><span>"dot"</span><span>],</span><span> </span><span>"h*t"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>],</span><span> </span><span>"ho*"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>],</span><span> </span><span>"d*t"</span><span>:</span><span> </span><span>[</span><span>"dot"</span><span>],</span><span> </span><span>"do*"</span><span>:</span><span> </span><span>[</span><span>"dot"</span><span>,</span><span> </span><span>"dog"</span><span>],</span><span> </span><span>"*og"</span><span>:</span><span> </span><span>[</span><span>"dog"</span><span>,</span><span> </span><span>"cog"</span><span>],</span><span> </span><span>"c*g"</span><span>:</span><span> </span><span>[</span><span>"cog"</span><span>],</span><span> </span><span>"co*"</span><span>:</span><span> </span><span>[</span><span>"cog"</span><span>]</span><span> </span><span>}</span><span> </span>
<span>{</span><span> </span><span>"*ot"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>,</span><span> </span><span>"dot"</span><span>],</span><span> </span><span>"h*t"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>],</span><span> </span><span>"ho*"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>],</span><span> </span><span>"d*t"</span><span>:</span><span> </span><span>[</span><span>"dot"</span><span>],</span><span> </span><span>"do*"</span><span>:</span><span> </span><span>[</span><span>"dot"</span><span>,</span><span> </span><span>"dog"</span><span>],</span><span> </span><span>"*og"</span><span>:</span><span> </span><span>[</span><span>"dog"</span><span>,</span><span> </span><span>"cog"</span><span>],</span><span> </span><span>"c*g"</span><span>:</span><span> </span><span>[</span><span>"cog"</span><span>],</span><span> </span><span>"co*"</span><span>:</span><span> </span><span>[</span><span>"cog"</span><span>]</span><span> </span><span>}</span><span> </span>
{ "*ot": ["hot", "dot"], "h*t": ["hot"], "ho*": ["hot"], "d*t": ["dot"], "do*": ["dot", "dog"], "*og": ["dog", "cog"], "c*g": ["cog"], "co*": ["cog"] }

Enter fullscreen mode Exit fullscreen mode

This will come in pretty handy when we’re trying to figure out the transformations.

Next step is to set up 2 queues to allow us to do BFS to find the shortest path. In my solution, I am initiating a search from both the beginning and the end. Honestly, it would not have occurred to me to do it that way except I have come across a problem like this before and saw this as a form of optimisation. I did try with and without this i.e. also doing the search only from the start. In the leetcode analysis, there wasn’t really much different but I am using the dual search since that’s what I learned and it doesn’t make it much more complicated.

So next step, setup 2 queues and 2 maps to track visited words (you can replace this with one to only traverse one way):


<span>qBegin</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>beginWord</span><span>,</span> <span>1</span><span>)])</span>
<span>qEnd</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>endWord</span><span>,</span> <span>1</span><span>)])</span>
<span>visitedBegin</span> <span>=</span> <span>{</span><span>beginWord</span><span>:</span> <span>1</span><span>}</span>
<span>visitedEnd</span> <span>=</span> <span>{</span><span>endWord</span><span>:</span> <span>1</span><span>}</span>
<span>qBegin</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>beginWord</span><span>,</span> <span>1</span><span>)])</span>
<span>qEnd</span> <span>=</span> <span>collections</span><span>.</span><span>deque</span><span>([(</span><span>endWord</span><span>,</span> <span>1</span><span>)])</span>

<span>visitedBegin</span> <span>=</span> <span>{</span><span>beginWord</span><span>:</span> <span>1</span><span>}</span>
<span>visitedEnd</span> <span>=</span> <span>{</span><span>endWord</span><span>:</span> <span>1</span><span>}</span>
qBegin = collections.deque([(beginWord, 1)])
qEnd = collections.deque([(endWord, 1)])

visitedBegin = {beginWord: 1}
visitedEnd = {endWord: 1}

Enter fullscreen mode Exit fullscreen mode

Traverse the queues using a while loop with popleft:


<span>while</span> <span>qBegin</span> <span>and</span> <span>qEnd</span><span>:</span>            
<span>while</span> <span>qBegin</span> <span>and</span> <span>qEnd</span><span>:</span>            
while qBegin and qEnd:

Enter fullscreen mode Exit fullscreen mode

Get the word and the current level in the queue:


<span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
<span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
word, level = queue.popleft()

Enter fullscreen mode Exit fullscreen mode

Iterate over each letter in that word and generate the keys to use in that map we preprocessed earlier:


<span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
        <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
<span>word</span><span>,</span> <span>level</span> <span>=</span> <span>queue</span><span>.</span><span>popleft</span><span>()</span>
    <span>for</span> <span>i</span> <span>in</span> <span>range</span><span>(</span><span>wordLength</span><span>):</span>
        <span>testWord</span> <span>=</span> <span>word</span><span>[:</span><span>i</span><span>]</span> <span>+</span> <span>"*"</span> <span>+</span> <span>word</span><span>[</span><span>i</span> <span>+</span> <span>1</span> <span>:]</span>
word, level = queue.popleft()
    for i in range(wordLength):
        testWord = word[:i] + "*" + word[i + 1 :]

Enter fullscreen mode Exit fullscreen mode

Now we check that map e.g. if we generated a word like “*ot”, based on our example earlier, we’d get back a list like: ["hot", "dot"]

Recall:


<span>{</span><span> </span><span>"*ot"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>,</span><span> </span><span>"dot"</span><span>],</span><span> </span><span>etc...</span><span> </span><span>}</span><span> </span>
<span>{</span><span> </span><span>"*ot"</span><span>:</span><span> </span><span>[</span><span>"hot"</span><span>,</span><span> </span><span>"dot"</span><span>],</span><span> </span><span>etc...</span><span> </span><span>}</span><span> </span>
{ "*ot": ["hot", "dot"], etc... }

Enter fullscreen mode Exit fullscreen mode

So in the following code:


<span>if</span> <span>testWord</span> <span>in</span> <span>combos</span><span>:</span>
            <span>for</span> <span>w</span> <span>in</span> <span>combos</span><span>[</span><span>testWord</span><span>]:</span>
                <span>if</span> <span>w</span> <span>in</span> <span>otherVisited</span><span>:</span>
                    <span>return</span> <span>level</span> <span>+</span> <span>otherVisited</span><span>[</span><span>w</span><span>]</span>
                <span>if</span> <span>w</span> <span>not</span> <span>in</span> <span>visited</span><span>:</span>
                    <span>visited</span><span>[</span><span>w</span><span>]</span> <span>=</span> <span>level</span> <span>+</span> <span>1</span>
                    <span>queue</span><span>.</span><span>append</span><span>((</span><span>w</span><span>,</span> <span>level</span> <span>+</span> <span>1</span><span>))</span>
<span>if</span> <span>testWord</span> <span>in</span> <span>combos</span><span>:</span>
            <span>for</span> <span>w</span> <span>in</span> <span>combos</span><span>[</span><span>testWord</span><span>]:</span>
                <span>if</span> <span>w</span> <span>in</span> <span>otherVisited</span><span>:</span>
                    <span>return</span> <span>level</span> <span>+</span> <span>otherVisited</span><span>[</span><span>w</span><span>]</span>
                <span>if</span> <span>w</span> <span>not</span> <span>in</span> <span>visited</span><span>:</span>
                    <span>visited</span><span>[</span><span>w</span><span>]</span> <span>=</span> <span>level</span> <span>+</span> <span>1</span>
                    <span>queue</span><span>.</span><span>append</span><span>((</span><span>w</span><span>,</span> <span>level</span> <span>+</span> <span>1</span><span>))</span>
if testWord in combos:
            for w in combos[testWord]:
                if w in otherVisited:
                    return level + otherVisited[w]
                if w not in visited:
                    visited[w] = level + 1
                    queue.append((w, level + 1))

Enter fullscreen mode Exit fullscreen mode

We would iterate over that list. If we discovered that word had already been visited in the other search, we would know that is was part of the path and we would have our answer return level + otherVisited[w].

If it was not visited, we would mark it as visited on this end visited[w] = level + 1 and add the word to the queue queue.append((w, level + 1)) and continue the search.

The time complexity here is basically the length of every word squared multiplied by the number of words. So if N is the number of word sand K is word length, we’d have:

O(K^2 * N)

The space complexity is basically the same. We stored K^2 * N in that map.

My solution here is not great I think. The coded is messy and the performance could certainly be optimised a lot more (only beat 50% of other submissions). Other things bother me like the method name I used getLadderLength doesn’t make sense but my brain is fried at this point so leaving it here. I hope I don’t ever get one like this in an interview!

January LeetCoding Challenge 2021 (33 Part Series)

原文链接：Day 9 – Word Ladder

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END