Leetcode[127] Word Ladder
09 Nov 2015###Task1 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 intermediate word must exist in the word list For example,
Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,”dot”,”dog”,”lot”,”log”] As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.
Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.
###Python
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
if not wordList or len(wordList) == 0:
return 0
queue = collections.deque()
queue.append(beginWord)
steps = 1
while len(queue) > 0:
size = len(queue)
for i in range(size):
cur = queue.popleft()
for j in range(len(cur)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
concat = cur[:j] + ch + cur[j + 1:]
if concat == endWord:
return steps + 1
if concat in wordList:
queue.append(concat)
wordList.remove(concat)
steps += 1
return 0
###Java
public class Solution {
public String replace(String s, int i, char c) {
char[] charArray = s.toCharArray();
charArray[i] = c;
return new String(charArray);
}
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
if (wordDict == null || wordDict.size() == 0) {
return 0;
}
LinkedList<String> queue = new LinkedList<String>();
queue.offer(beginWord);
wordDict.remove(beginWord);
int length = 1;
while (!queue.isEmpty()) {
int count = queue.size();
for (int j = 0; j < count; j++) {
String crt = queue.poll();
for (char c = 'a'; c <= 'z'; c++) {
for (int i = 0; i < crt.length(); i++) {
if (c == crt.charAt(i)) {
continue;
}
String replaced = replace(crt, i, c);
if (replaced.equals(endWord)) {
return length + 1;
}
if (wordDict.contains(replaced)) {
queue.offer(replaced);
wordDict.remove(replaced);
}
}
}
}
length++;
}
return 0;
}
}
###Points
- BFS search –> queue
- The way to move forward: check every character from ‘a’ to ‘z’, from first char to the last char.