A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words
beginWord -> s1 -> s2 -> ... -> sk
such that:
- Every adjacent pair of words differs by a single letter.
- Every si for
1 <= i <= kis in wordList. Note that beginWord does not need to be in wordList. sk == endWord
Given two words, beginWord and endWord, and a dictionary wordList,
return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Test Cases
Input:
(String) beginWord = "hit"
(String) endWord = "cog"
(String[]) wordList = ["hot","dot","dog","lot","log","cog"]
Output:
(int) 5
Input:
(String) beginWord = "hit"
(String) endWord = "cog"
(String[]) wordList = ["hot","dot","dog","lot","log"]
Output:
(int) 0
Solution
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(endWord)) {
return 0;
}
queue<string> q;
q.push(beginWord);
int steps = 0;
while(!q.empty()) {
int qs = q.size();
for(int i=0; i<qs; i++) {
string s = q.front();
q.pop();
if (s == endWord) return steps+1;
for(int j=0; j<s.length(); j++) {
char orig = s[j];
for(char k='a'; k<='z'; k++) {
s[j] = k;
if (wordSet.count(s)) {
q.push(s);
wordSet.erase(s);
}
}
s[j] = orig;
}
}
steps++;
}
return 0;
}
};class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) {
return 0;
}
Queue<String> q = new LinkedList<>();
q.offer(beginWord);
int steps = 0, n = beginWord.length();
while(!q.isEmpty()) {
int qs = q.size();
for(int i=0; i<qs; i++) {
StringBuilder sb = new StringBuilder(q.poll());
if (endWord.equals(sb.toString())) {
return steps+1;
}
for(int j=0; j<n; j++) {
char orig = sb.charAt(j);
for(char k='a'; k<='z'; k++) {
sb.setCharAt(j, k);
if (set.contains(sb.toString())) {
q.offer(sb.toString());
set.remove(sb.toString());
}
}
sb.setCharAt(j, orig);
}
}
steps++;
}
return 0;
}
}