Word ladder complexity analysis

Question

I'd like to make sure that I am doing the time complexity analysis correctly. There seems to be many different analysis.

Just in case people don't know the problem this is problem description.

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

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. For example,

Given:

beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

And this is simple BFS algorithm.

    static int ladderLength(String beginWord, String endWord, List<String> wordList) {
    int level = 1;
    Deque<String> queue = new LinkedList<>();
    queue.add(beginWord);
    queue.add(null);
    Set<String> visited = new HashSet<>();
    // worst case we can add all dictionary thus N (len(dict)) computation
    while (!queue.isEmpty()) {
        String word = queue.removeFirst();
        if (word != null) {
            if (word.equals(endWord)) {
                return level;
            }
            // m * 26 * log N
            for (int i = 0; i < word.length(); i++) {
                char[] chars = word.toCharArray();
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    String newStr = new String(chars);
                    if (!visited.contains(newStr) && wordList.contains(newStr)) {
                        queue.add(newStr);
                        visited.add(newStr);
                    }
                }
            }
        } else {
            level++;
            if (!queue.isEmpty()) {
                queue.add(null);
            }
        }
    }
    return 0;
}

wordList (dictionary) contains N elements and length of beginWord is m

In worst case, the queue would have all the element in the word list, thus, the outer while loop would run for o(N). For each word (length m), it tries 26 charaters (a to z) thus inner nested for loop is o(26*m), and inside inner for loop, it does wordList.contains assume it's o(logN). So overall it's o(N*m*26*logN) => o(N*mlogN) Is this correct?

Answer 1

The List<T> type does not automatically sort its elements, but instead "faithfully" keeps all elements in the order they were added. So wordList.contains is in fact O(n). However for a HashSet such as visited, this operation is O(1) (amortized), so consider switching to that.