Accepted Swift solution with full comments


  • 0
    M

    This is only solution I managed to get accept in Swift. In Swift 3, working with characters within Strings is severely limited because Strings aren't directly indexable. We have to pay a heavy price to convert to Character arrays on each check. My solution stores this result to avoid paying the cost repeatedly. This will improve with Swift 4 Strings, but in 3, we just have to deal it:

    class Solution {
        func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
            // ensure the endWord is in the wordList
            if !wordList.contains(endWord) {
                return 0
            }
    
            // build a word map with char array representations
            // this saves an enormous amount of time
            var wordMap: [String: [Character]] = [:]
            for i in 0..<wordList.count {
                // beginWord should never be in the list
                if wordList[i] == beginWord {
                    continue
                }
                wordMap[wordList[i]] = [Character](wordList[i].characters)
            }
            
            // we work the problem from the begining forward and end backwards
            // this allows us to deal with the smallest set of possibilities in 
            // both "directions"
            var beginMap:[String: [Character]] = [beginWord: [Character](beginWord.characters)]
            var endMap:[String: [Character]] = [endWord: [Character](endWord.characters)]
            
            // burnedMap bridges what has been used in both beginMap or endMap
            var burnedMap:[String: [Character]] = [:]
            
            // word len is stable throughout the iterations, pay for it only once
            let wordLen = beginWord.count
            
            // mutations tracts how many time mutated on the road from beginWord to endWord
            var mutations = 1
    
            // we continue while beginMap and endMap are non-empty
            // if one empties, there is no path from beginWord to endWord
            while !beginMap.isEmpty && !endMap.isEmpty {
                // minimize the working set by swapping in the smaller
                // set, we only care about the mutation count
                if beginMap.count > endMap.count {
                    let tempMap = beginMap
                    beginMap = endMap
                    endMap = tempMap
                }
    
                // track the upcoming set of mutation candidates we're about to create
                var newMap: [String: [Character]] = [:]
    
                // iterate throught he last set of mutation candidates
                for candidateKV in beginMap {
                    let candidateChars = candidateKV.value
                    
                    // walk through all the remaining (un-burned) valid words
                    for wordKV in wordMap {
                        let word = wordKV.key
                        let wordChars = wordKV.value
                        
                        // diff the candidate and valid words looking
                        // fir diffs of 1 character
                        var diffs = 0
                        
                        for i in 0..<wordLen {
                            if candidateChars[i] != wordChars[i] {
                                diffs += 1
                                if diffs > 1 {
                                    break
                                }
                            }
                        }
                        
                        // anything other than a diff of 1 is not applicable
                        // in this loop, we can only consider "word" if the
                        // diff is exactly 1
                        if diffs == 1 {
                            // we have a valid 1 character diff, use it
                            
                            if endMap[word] != nil {
                                // base case reached
                                return mutations + 1
                            }
                            
                            if burnedMap[word] == nil {
                                newMap[word] = wordChars
                                burnedMap[word] = wordChars
                            }
                        }
                    }
                }
                
                // we already evaluated what was in beginMap, we can 
                // lose those and use the newMap evaluation set 
                beginMap = newMap
                
                // we have completed an additional mutation step
                mutations += 1
            }
            
            return 0
        }
    }  
    

Log in to reply
 

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