swift – 从一个单词走到另一个单词的更快的解决方案

我做了一个具有较长设置时间的例子,但是一旦完成了单词索引,单词链结果几乎是瞬时的.

// --- wordPath.swift ---

// create a list of link patterns for a word
// ------------------------------------------
// A link pattern is an ordered list of letters in a word where one letter is missing
//
// This corresponds to a combination of letters that can from the word
// by adding a single letter and,conversely to combinations of letters that
// are possible by removing a letter from the word
//
// Letters are sorted alphabetically in order to ignore permutations
//
// for example:   
//
//   "corner" has 6 link patterns (one of which is a duplicate)
//                
//   the sorted letters are : "cenorr"
//
//   the links are the 6 combinations of 5 out of 6 letters of "cenorr"
//   with letters kept in alphabetical order.
//
//   because letters are sorted,the combinations can be obtained by
//   removing one letter at each position.
//
//   removing position 1 : enorr
//   removing position 2 : cnorr
//   removing position 3 : ceorr
//   removing position 4 : cenrr 
//   removing position 5 : cenor 
//   removing position 6 : cenor (this is the duplicate)
//  
public func linksOfWord(_ word:String)->[String]
{
  var result:[String] = []

  // sort letters
  let sortedLetters = word.characters.sorted()

  // return one string for each combination of N-1 letters
  // exclude duplicates (which will always be consecutive)
  var wordLink = ""
  for skipChar in sortedLetters.indices
  { 
    let nextLink = String(sortedLetters[0..<skipChar]) 
                 + String(sortedLetters[skipChar+1..<sortedLetters.count]) 
    if nextLink == wordLink { continue }

    wordLink = nextLink
    result.append(wordLink)
  }

  return result
}


// Create an index of wordlinks to the words that can be fromed from them
// ----------------------------------------------------------------------
// - The wordLinks dictionary contains a list of all the words that can be formed
//   by adding one letter to a given link pattern
// - This is essentially the reverse of linksOfWord for all words in the dictionary
// - note: Swift will use lazy initialization for this global variable,only executing the closure once.
//
public var wordsOfLink:[String:[String]] = 
{
  var result:[String:[String]] = [:]

  // get all words
  let wordList = try! String(contentsOfFile: "/usr/share/dict/words")
                      .lowercased()
                      .components(separatedBy:"n")

  // add each word to the index of its wordLinks                        
  for word in wordList
  {
     for wordLink in linksOfWord(word)
     {
        result[wordLink] = (result[wordLink] ?? []) + [word]
     }
  }

  return result   
}()

// Iteration counted,for comparison with OP
public var iterations = 0

// word path seeking algorithm
// ---------------------------
// - Go through word paths using linksOfWord and wordsOfLink as a virtual tree structure
//   linksOfWord("word") -> 1:N array of links -> wordsOfLink("Link") -> 1:N array of words
// - Performs a breadth-first tree search by exausting shorter path lengths before moving on to longer ones
// - Simultaneously search forward and backward to minimize the exponential nature of path expansions
//

public func findWordPath(from fromWord:String,to toWord:String,shortestPath:Bool=false) -> [String]?
{
   iterations = 0

   // both words must be same length
   guard fromWord.characters.count == toWord.characters.count
   else  { return nil }

   // processing in lowercase only
   let startWord = fromWord.lowercased()
   let endWord   = toWord.lowercased()

   // keep track of links already processed (avoid infinite loops)
   var seenLinks = Set<String>() 
   var seenWords = Set<String>()

   // path expansion from starting word forward to ending word  
   var forwardLinks:[String:[String]] = [:]           // links that have a forward path connecting to the starting word
   var forwardPaths                   = [[startWord]] // partial forward paths to examine
   var forwardIndex                   = 0             // currently examined forwardPath (index) 

   // path expansion from ending word backward to starting word
   var backwardLinks:[String:[String]] = [:]            // links that have a backward path connecting to the ending word
   var backwardPaths                   = [[endWord]]    // partial backward paths to examine
   var backwardIndex                   = 0              // currently examined backwardPath (index)

   // establish initial links to start and end words 
   // - allows logic to only check path to path connections 
   //   (and not path to word in addition to it)
   linksOfWord(startWord).forEach{forwardLinks[$0] = [startWord]}
   linksOfWord(endWord).forEach{backwardLinks[$0]  = [endWord]}


   // Explore shorter paths in each direction before moving on to longer ones
   // This improves performance but does not guarantee the shortest word path 
   // will be selected when a connection is found 
   // e.g. forward(4)->backward(3) could be found before backward(4)->forward(2)
   //      resulting in a 7 word path when a 6 word path exists.
   // Finding the shortest possible word path requires that we explore forward only
   // (which is what the shortestPath parameter controls)
   var currentLength = 1

   // Examine partial word paths in multiple passes with an increasing path length (currentLength)
   // - For each path length,check if forward and backward paths can connect to one another.
   // - For each length,forwardIndex and backwardIndex advance through the paths
   //   of the current length thus exhausting both forward and backward paths of that length
   //   before moving on to the next length.
   // - As paths of the current length are examined,the partial path arrays receive new (longer) word paths
   //   to examine. 
   // - The added paths have 1 additional word which creates a new group of paths for the next pass
   //   at currentLength + 1
   // - When none of the partial word paths can be extended by adding a word that was not seen before
   //   the forward or backward path array will stop growing and the index will reach the end of the array
   //   indicating that no word path exists between start and end words
   while forwardIndex < forwardPaths.count 
         && ( backwardIndex < backwardPaths.count || shortestPath )
   {
       // Examine forward path links (of current length) for connection
       // to the end word or to a backward path that connects to it
       while forwardIndex < forwardPaths.count
          && forwardPaths[forwardIndex].count == currentLength
       {
          let forwardPath = forwardPaths[forwardIndex]

          forwardIndex   += 1
          iterations     += 1

          // expand links for last word of "forward" path
          for wordLink in linksOfWord(forwardPath.last!) 
          {
             // link connects to a backward path,return the combined forward and backward paths
             if let backwardPath = backwardLinks[wordLink]
             { return forwardPath + backwardPath }

             // don't explore links that have already been examined
             if !seenLinks.insert(wordLink).inserted
             { continue }

             // record forward path to allow linking from backward paths
             // i.e. this link is known to lead to the starting word (through forwardPath)
             if !shortestPath
             { forwardLinks[wordLink] = forwardPath }

             // for all words that can be created by adding one letter to the word link   
             // add new forward paths to examine on the next length pass
             for word in wordsOfLink[wordLink] ?? []
             { 
               if seenWords.insert(word).inserted
               {
                 forwardPaths.append(forwardPath + [word])
               }
             }
          } 
       }

       // Examine backward path links (of current length) for connection
       // to the start word or to a forward path that connects to it
       // allowing one length backward path to support unknown end words
       while !shortestPath
          && backwardIndex < backwardPaths.count
          && backwardPaths[backwardIndex].count == currentLength
       {
          let backwardPath = backwardPaths[backwardIndex]

          backwardIndex   += 1
          iterations      += 1

          // expand links for first word of "backward" path
          for wordLink in linksOfWord(backwardPath.first!)
          {
             // link connects to starting path,combine and return result
             if let forwardPath = forwardLinks[wordLink]
             { return forwardPath + backwardPath }

             // don't explore links that have already been examined
             if !seenLinks.insert(wordLink).inserted
             { continue }

             // record backward path to allow linking from forward paths
             // i.e. this link is known to lead to the ending word (through backwardPath)
             backwardLinks[wordLink] =  backwardPath

             // for all words that can be created by adding one letter to the word link   
             // add new backward paths to examine on the next length pass
             for word in wordsOfLink[wordLink] ?? []
             { 
                if seenWords.insert(word).inserted
                {
                  backwardPaths.append( [word] + backwardPath ) 
                }
             }
          } 
       }

       // all forward and backward paths of currentLength have been examined
       // move on to next length
       currentLength += 1
   }

   // when either path list is exausted,there are no possible paths.
   return nil
}

…

// --- Playground ---

// compute word path and print result
func printWordPath(_ firstWord:String,_ lastWord:String)
{
  print("    printWordPath("(firstWord)","(lastWord)")")

  let startTime = ProcessInfo().systemUptime
  if let foundPath = findWordPath(from:firstWord,to:lastWord,shortestPath:false)
  { 
    let time = String(format:"%.5f",ProcessInfo().systemUptime-startTime)
    print("    //(foundPath.count) words :  (foundPath)n    //        (iterations) iterations,(time) sec ")
  }
  else
  { print("    // No Path Found between (firstWord) and (lastWord)") }
  print("")
}

printWordPath("bat","man")
// 3 words :  ["bat","amt","man"]
//        16 iterations,6.34718 sec <-- longer time here because of initializations

printWordPath("many","shop")
// 5 words :  ["many","hymn","homy","hypo","shop"]
//        154 iterations,0.00752 sec 

printWordPath("many","star")
// 4 words :  ["many","maty","mast","star"]
//        101 iterations,0.00622 sec 

printWordPath("define","system")
// 6 words :  ["define","fenite","entify","feisty","stymie","system"]
//        574 iterations,0.02374 sec 

printWordPath("defend","oppose")
// 6 words :  ["defend","depend","depone","podeon","pooped","oppose"]
//        336 iterations,0.01273 sec 

printWordPath("alphabet","integers")
// 7 words :  ["alphabet","lapithae","apterial","epistlar","splinter","sterling","integers"]
//        1057 iterations,0.04454 sec 

printWordPath("Elephant","Microbes")
// 8 words :  ["elephant","antelope","lapstone","parsonet","somepart","imposter","comprise","microbes"]
//        2536 iterations,0.10133 sec 

printWordPath("Microbes","Elephant")
// 8 words :  ["microbes","persicot","petrolic","copalite","pectinal","planchet","elephant"]
//        2232 iterations,0.09649 sec 

printWordPath("Work","Home")
// 4 words :  ["work","worm","mohr","home"]
//        52 iterations,0.00278 sec 

printWordPath("Head","Toes")
// 4 words :  ["head","ahet","ates","toes"]
//        146 iterations,0.00684 sec 

printWordPath("North","South")
// 3 words :  ["north","horst","south"]
//        22 iterations,0.00189 sec 

printWordPath("Employee","Pesident")
// 7 words :  ["employee","employed","redeploy","leporide","pedelion","disponee","pesident"]
//        390 iterations,0.01810 sec 

printWordPath("Yellow","Orange")
// 5 words :  ["yellow","lowery","royale","royena","orange"]
//        225 iterations,0.01025 sec 

printWordPath("Whale","shark")
// 4 words :  ["whale","hawse","asher","shark"]
//        94 iterations,0.00473 sec 

printWordPath("Police","Fellon")
// 4 words :  ["police","pinole","lionel","fellon"]
//        56 iterations,0.00336 sec 

printWordPath("religion","insanity")
// 6 words :  ["religion","triolein","reinstil","senility","salinity","insanity"]
//        483 iterations,0.02411 sec 

printWordPath("ebony","ivory")
// 4 words :  ["ebony","eryon","irony","ivory"]
//        53 iterations,0.00260 sec 

printWordPath("electronic","mechanical")
// 7 words :  ["electronic","citronelle","collineate","tellinacea","chatelaine","atechnical","mechanical"]
//        316 iterations,0.01618 sec 

printWordPath("detrimental","appropriate")
// 7 words :  ["detrimental","pentremital","interpolate","interportal","prerational","preparation","appropriate"]
//        262 iterations,0.01319 sec

请注意,这可以找到最后两个示例的解决方案,我也注意到很多 – > mand – >主要 – >说 – > …正在替换从“主要”到“说”的两个字母,所以我最终得到了一条不同的路径.

顺便说一句,我把这些函数放在操场上的一个单独的文件中(在Sources下),因为行执行的计数使执行速度变慢到爬行速度.

[编辑]改变迭代次数使其与OP的代码计数方式更加一致.添加了更多示例(对此有太多乐趣).

[编辑]改编为Swift 3,增加了对逻辑的更多解释,进一步简化/优化了代码.