Word Ladder – Python 3 (Week 14 – 03)

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):
        # write your code here
        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) : not forget the complexity of word[:i]
    # 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 char == word[i]:
                    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):
        # write your code here
        dict.add(end)
        queue = collections.deque([start])
        
        distance = {start: 1}

        while queue:
            word = queue.popleft()
            if word == end:
                return distance[word]
                
            for next_word in self.get_next_words(word):
                if next_word in distance or next_word not in dict:
                    continue
                queue.append(next_word)
                distance[next_word] = distance[word] + 1
                
            
        return 0
        
    # O(26 * L^2) : not forget the complexity of word[:i]
    # 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 char == word[i]:
                    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):
        # write your code here
        dict.add(end)
        queue1, queue2 = collections.deque([start]), collections.deque([end])
        visited1, visited2 = set([start]), set([end])
        distance = 1

        while queue1 or queue2:
            
            distance += 1
            for _ in range(len(queue1)):
                word = queue1.popleft()
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited1:  
                        continue
                    if next_word in visited2: 
                        return distance
                    visited1.add(next_word)
                    queue1.append(next_word)

            distance += 1
            for _ in range(len(queue2)):
                word = queue2.popleft()
                for next_word in self.get_next_words(word):
                    if next_word not in dict or next_word in visited2:  
                        continue
                    if next_word in visited1:  
                        return distance
                    visited2.add(next_word)
                    queue2.append(next_word)
    
        return 0
        
        
        
   
        
    # O(26 * L^2) : not forget the complexity of word[:i]
    # 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 char == word[i]:
                    continue
                words.append(left + char + right)
        return words