title: Time complexity of this algorithm: Word Ladder
body: <p>Question:</p>
  
  <blockquote>
    <p>Given two words (beginWord and endWord), and a dictionary's word list,
    find all shortest transformation sequence(s) from beginWord to
    endWord, such that:</p>
    
    <p>Only one letter can be changed at a time. Each transformed word must
    exist in the word list. Note that beginWord is not a transformed word.</p>
    
    <p>Example 1:</p>
    
    <p>Input: beginWord = "hit", 
    endWord = "cog", 
    wordList =
    ["hot","dot","dog","lot","log","cog"]</p>
    
    <p>Output: [   ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]</p>
  </blockquote>
  
  <p>My solution is based on this idea, but how do I analyze the time and space complexity of this solution?</p>
  
  <blockquote>
    <p>1) Perform a BFS starting at beginWord by transforming every letter to one of 26 letters, and see if the transformed word is in the wordList, if so, put in queue.</p>
    
    <p>2) During BFS, maintain a graph of {word:nextWord} for all valid next
    words </p>
    
    <p>3) When a nextWord reaches endWord, do a backtracking DFS (pre-order
    traversal) on the graph to get all paths.</p>
  </blockquote>
  
  <pre><code>class Solution:
      def findLadders(self, beginWord, endWord, wordList):
          """
          :type beginWord: str
          :type endWord: str
          :type wordList: List[str]
          :rtype: List[List[str]]
          """
          wordListSet = set(wordList+[beginWord])
          graph = collections.defaultdict(list)
          q = set([beginWord])    
          count = 0
          result = []
          while q:
              count +=1
              newQ = set()
              for word in q:
                  wordListSet.remove(word)
              for word in q:
                  if word == endWord:                                        
                      self.getAllPaths(graph, beginWord, endWord, result, [])
                      return result
                  for i in range(len(word)):
                      for sub in 'abcdefghijklmnopqrstuvwxyz':
                          if sub != word[i]:
                              newWord = word[:i] + sub + word[i+1:]
                              if newWord in wordListSet:
                                  graph[word].append(newWord)
                                  newQ.add(newWord)
              q = newQ
          return []
  
      def getAllPaths(self, graph, node, target, result, output):
          #This is just a backtracking pre-order traversal DFS on a DAG.
          output.append(node)
          if node==target:
              result.append(output[:])
          else:
              for child in graph[node]:
                  self.getAllPaths(graph,child, target, result, output)
                  output.pop()
  </code></pre>
  
  <p>I have a hard time coming up with the time and space complexity of it.
  My contention: </p>
  
  <p>Time: <code>O(26*L*N + N</code>), where <code>L</code> is <em>average length</em> of each word, and <code>N</code> is the <em>number of words in the wordList</em>. Worst case here is every word transformed happens to be in the list, so each transformation needs <code>26 * length of word</code>. The DFS part is just <code>O(N)</code>. So asymptotically it's just <code>O(L*N)</code></p>
  
  <p>Space: O(N)</p>