[leetcode] 3-12 회차

날이 많이 더워졌다. 그만큼 새들도 많이 보여서 좋다. 한국에 살아서 최고의 복지는 예쁜 원앙들을 쉽게 볼 수 있다는 점도 포함되어 있을 것이다.

 

https://leetcode.com/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """
        
        s= set(wordList)
        
        if endWord not in s and endWord != beginWord:
            return 0

        word_cnt = len(beginWord)
        
        q = collections.deque([(beginWord, 0)])
        
        v = {beginWord}
        alphabet =  "abcdefghijklmnopqrstuvwxyz"
        while q:
            
            word, cnt = q.popleft()
            if word == endWord:
                return cnt+1

            for i in range(word_cnt):
                for alpha in alphabet:
                    if  word[i] != alpha:
                        n_word = word[:i] + alpha + word[i+1:]
                        if n_word in s and n_word not in v:
                            v.add(n_word)
                            q.append((n_word, cnt+1))

        return 0