Question: https://oj.leetcode.com/problems/word-ladder/
Question Name: Word Ladder
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | class Solution: # @param start, a set of string # @return two dictionaries def _buildSig(self, contents): sig = {} # Records the signatures for each string bucket = {} # Records the strings with each signature for string in contents: sig[string] = [] for index in xrange(len(string)): tempSig = string[:index] + "*" + string[index+1:] sig[string].append(tempSig) if tempSig not in bucket: bucket[tempSig] = [] bucket[tempSig].append(string) return sig, bucket # @param start, a string # @param end, a string # @param dict, a set of string # @return an integer def ladderLength(self, start, end, dict): # Build the graph. # Two nodes (whose value is the string in dict), are connected if # they have one same signature or more. sig, bucket = self._buildSig(set([start, end]) | dict) accessed = {} for string in dict: accessed[string] = False accessed[start] = True # Travel the graph in breadth-first search. currentLayer = [start] steps = 1 while len(currentLayer) != 0: steps += 1 nextLayer = [] for intermediate in currentLayer: signatures = sig[intermediate] for signature in signatures: for nextLayerCandidate in bucket[signature]: # Transformation from start to end finished. if nextLayerCandidate == end: return steps # Accessed before. Not to access again. if accessed[nextLayerCandidate]: continue accessed[nextLayerCandidate] = True nextLayer.append(nextLayerCandidate) currentLayer = nextLayer return 0 |