Leetcode 127. Word Ladder

https://leetcode.com/problems/word-ladder/

This is much easier than the last one.

Solution:

# T:O(n*d) S:O(d)
class Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string!!!dict is a set type!!!
    # @return an integer
    def ladderLength(self, start, end, dict):
        dict.add(end)
        q = []
        q.append((start, 1))
        while q:
            curr = q.pop(0)
            currword = curr[0]; currlen = curr[1]
            if currword == end: return currlen
            for i in range(len(start)):
                part1 = currword[:i]; part2 = currword[i+1:]
                for j in 'abcdefghijklmnopqrstuvwxyz':
                    if currword[i] != j:
                        nextword = part1 + j + part2
                        if nextword in dict:
                            q.append((nextword, currlen+1)); 
                            dict.remove(nextword)
        return 0

Run Time: 552 ms