Golang solution using BFS


  • 0

    We first create a word dictionary and then for beginWord, check all variants (modify one character from a to z) is contained in the dictionary using BFS search.

    func ladderLength(beginWord string, endWord string, wordList []string) int {
    	wordMap := getWordMap(wordList, beginWord)
    	que := []string{beginWord}
    	depth := 0
    	for len(que) > 0 {
    		depth++
    
    		qlen := len(que)
    		for i := 0; i < qlen; i++ {
    			word := que[0]
    			que = que[1:]
    
    			candidates := getCandidates(word)
    			for _, candidate := range candidates {
    				if _, ok := wordMap[candidate]; ok {
    					if candidate == endWord {
    						return depth + 1
    					}
    
    					delete(wordMap, candidate)
    					que = append(que, candidate)
    				}
    			}
    		}
    	}
    	return 0
    }
    
    func getWordMap(wordList []string, beginWord string) map[string]int {
    	wordMap := make(map[string]int)
    	for i, word := range wordList {
    		if _, ok := wordMap[word]; !ok {
    			if word != beginWord {
    				wordMap[word] = i
    			}
    		}
    	}
    	return wordMap
    }
    
    func getCandidates(word string) []string {
    	var res []string
    	for i := 0; i < 26; i++ {
    		for j := 0; j < len(word); j++ {
    			if word[j] != byte(int('a')+i) {
    				res = append(res, word[:j]+string(int('a')+i)+word[j+1:])
    			}
    		}
    	}
    	return res
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.