from collections import deque

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dictionary):
        # write your code here
        if start == end:
            return 1

        dictionary.add(end)
        steps = {start:1}
        queue = deque([start])

        while queue:
            word = queue.popleft()
            if word == end:
                return steps[word]

            for candidate in self._next_words(word):

                if candidate not in dictionary or candidate in steps:
                    continue

                queue.append(candidate)
                steps[candidate] = steps[word] + 1
 
        return 0

    # O(26 * L^2)
    # L is the length of word
    def _next_words(self, word):
        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                words.append(left + char + right)
        return words


# 分层遍历

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        dict.add(end)
        queue = collections.deque([start])
        visited = set([start])
        
        distance = 0
        while queue:
            distance += 1
            for i in range(len(queue)):
                word = queue.popleft()
                if word == end:
                    return distance
                
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited:
                        continue
                    queue.append(next_word)
                    visited.add(next_word) 

        return 0
        
    # O(26 * L^2)
    # L is the length of word
    def get_next_words(self, word):
        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                words.append(left + char + right)
        return words

from collections import deque

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dictionary):
        # write your code here
        if start == end:
            return 1

        dictionary.add(end)
        steps = {start:1}
        queue = deque([start])

        while queue:
            word = queue.popleft()
            if word == end:
                return steps[word]

            for candidate in self._next_words(word):

                if candidate not in dictionary or candidate in steps:
                    continue

                queue.append(candidate)
                steps[candidate] = steps[word] + 1
 
        return 0

    # O(26 * L^2)
    # L is the length of word
    def _next_words(self, word):
        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                words.append(left + char + right)
        return words


# 分层遍历

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: An integer
    """
    def ladderLength(self, start, end, dict):
        dict.add(end)
        queue = collections.deque([start])
        visited = set([start])
        
        distance = 0
        while queue:
            distance += 1
            for i in range(len(queue)):
                word = queue.popleft()
                if word == end:
                    return distance
                
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited:
                        continue
                    queue.append(next_word)
                    visited.add(next_word) 

        return 0
        
    # O(26 * L^2)
    # L is the length of word
    def get_next_words(self, word):
        words = []
        for i in range(len(word)):
            left, right = word[:i], word[i + 1:]
            for char in 'abcdefghijklmnopqrstuvwxyz':
                if word[i] == char:
                    continue
                words.append(left + char + right)
        return words

@param: start: a string     @param: end: a string     @param: dict: a set of string     @return: An integer # write your code here # O(26 * L^2) # L is the length of word # 分层遍历 @param: start: a string     @param: end: a string     @param: dict: a set of string     @return: An integer # O(26 * L^2) # L is the length of word