LeetCode [127] Word Ladder

 127. Word Ladder

Medium

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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

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

Output: 5

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

Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

//C++: 308ms class Solution { public: int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) { queue<pair<string, int>> que; que.push(pair<string, int>(beginWord, 1)); int n = beginWord.size(); while(!que.empty()){ string w = que.front().first; int cur_step = que.front().second; que.pop(); for(int i=0; i<n; ++i){ string ww = w; for(char c='a'; c<='z'; ++c){ ww[i] = c; if(ww==endWord){ return cur_step+1; }else if(wordDict.find(ww)!=wordDict.end()){ wordDict.erase(ww); que.push(pair<string, int>(ww, cur_step+1)); } } } } } }; //Java class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { int sz = beginWord.length(); Queue<String> que = new LinkedList<>(); int step = 0; Set<String> dict = new HashSet<>(); for (String w : wordList) dict.add(w); que.add(beginWord); dict.remove(beginWord); while (!que.isEmpty()) { int len = que.size(); for (int k = 0; k < len; ++k) { String w = que.poll(); if (w.equals(endWord)) return step + 1; for (int i = 0; i < sz; ++i) { for (char c = 'a'; c <= 'z'; ++c) { StringBuilder sb = new StringBuilder(w); sb.setCharAt(i, c); if (dict.contains(sb.toString())) { que.add(sb.toString()); dict.remove(sb.toString()); } } } } step++; } return 0; } }