Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

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

 

Constraints:

  • 1 <= beginWord.length <= 10
  • 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 words in wordList are unique.
SOLUTION:
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        n = len(beginWord)
        wordList = set(wordList + [beginWord])
        graph = {}
        for word in wordList:
            for i in range(n):
                for c in "abcdefghijklmnopqrstuvwxyz":
                    currstr = word[0:i] + c + word[i+1:]
                    if currstr != word and currstr in wordList:
                        if word in graph:
                            graph[word].append(currstr)
                        else:
                            graph[word] = [currstr]
        dist = {}
        dist[beginWord] = 1
        queue = [(beginWord, 1)]
        visited = set()
        i = 0
        while i < len(queue):
            curr, k = queue[i]
            for j in graph.get(curr, []):
                if j not in visited:
                    dist[j] = dist.get(curr, float('inf')) + 1
                    if j == endWord:
                        return k + 1
                    visited.add(j)
                    queue.append((j, k + 1))
            i += 1
        return 0

Comments

Post a Comment

Popular posts from this blog

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more

Sliding Window GCD

Sliding Window GCD Sliding Window GCD Problem Description You are given an array of integers nums of length N . There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an array of length N - k + 1 representing the GCD of each subarray of length k from left to right. Solution Approach The solution to this problem involves implementing a special queue data structure using two stacks. This special queue allows the push , pop , and GCD operations in O(1) amortized time complexity. The implementation of this queue is based on the combination of two existing techniques: implementing a queue using stacks and implementing a stack that stores GCD values. By using this special queue, we can efficiently calculate the GCD for each sliding window in O(N) time complexity. This technique is useful to understand the impl...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more