LeetCode – Word Ladder
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
Note:
There is an edge between two vertices, if and only if they differ by exactly one character. Now we are asked to find the length of the shortest path from start to end, which is readily solved by breadth-first search.
We can build the graph in init step, or on the fly.
Another way is to try all the strings that are different from the current string by one character. Since the characters are lowercase, the number of such strings is25n , which is acceptable.
X. Two-end BFS
https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
X. BFS
https://linchicoding.wordpress.com/2014/10/13/leetcode-word-ladder/
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) { Set<String> reached = new HashSet<String>(); reached.add(beginWord); wordDict.add(endWord); int distance = 1; while(!reached.contains(endWord)) { Set<String> toAdd = new HashSet<String>(); for(String each : reached) { for (int i = 0; i < each.length(); i++) { char[] chars = each.toCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { chars[i] = ch; String word = new String(chars); if(wordDict.contains(word)) { toAdd.add(word); wordDict.remove(word); } } } } distance ++; if(toAdd.size() == 0) return 0; reached = toAdd; } return distance; }
https://linchicoding.wordpress.com/2014/10/13/leetcode-word-ladder/
X. Two-End BFS
https://discuss.leetcode.com/topic/10372/share-my-two-end-bfs-in-c-80ms/9
https://leetcode.com/discuss/68935/two-end-bfs-in-java-31ms
Convert this problem to a math problem: Find a shortest path from one Vertex to another in a graph. Then searching from both Vertexes always visits less Vertexes than searching from one Vertex. But I can't prove this theory
using two ends by alternating beginSet and endSet
you are replacing a big search tree in the one-end solution with two smaller trees in the two-end solution. Both solutions have the same TOTAL depth, yet tree width grows exponentially w.r.t. depths, and the two-end solutions results in less nodes being visited.
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();
int len = 1;
int strLen = beginWord.length();
HashSet<String> visited = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> set = beginSet;
beginSet = endSet;
endSet = set;
}
Set<String> temp = new HashSet<String>();
for (String word : beginSet) {
char[] chs = word.toCharArray();
for (int i = 0; i < chs.length; i++) {
for (char c = 'a'; c <= 'z'; c++) {
char old = chs[i];//
chs[i] = c;//
String target = String.valueOf(chs);
if (endSet.contains(target)) {
return len + 1;
}
if (!visited.contains(target) && wordList.contains(target)) {
temp.add(target);
visited.add(target);
}
chs[i] = old;//\\
}
}
}
beginSet = temp;
len++;
}
return 0;
}
Two-End BFS recusion
https://discuss.leetcode.com/topic/17956/super-fast-java-solution-using-two-end-bfs
Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
Note:
- Return 0 if there is no such transformation sequence.
- All words have the same length.
- All words contain only lowercase alphabetic characters.
There is an edge between two vertices, if and only if they differ by exactly one character. Now we are asked to find the length of the shortest path from start to end, which is readily solved by breadth-first search.
We can build the graph in init step, or on the fly.
Another way is to try all the strings that are different from the current string by one character. Since the characters are lowercase, the number of such strings is
X. Two-end BFS
https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();
int len = 1;
int strLen = beginWord.length();
HashSet<String> visited = new HashSet<String>();
beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> set = beginSet;
beginSet = endSet;
endSet = set;
}
Set<String> temp = new HashSet<String>();
for (String word : beginSet) {
char[] chs = word.toCharArray();
for (int i = 0; i < chs.length; i++) {
for (char c = 'a'; c <= 'z'; c++) {
char old = chs[i];
chs[i] = c;
String target = String.valueOf(chs);
if (endSet.contains(target)) {
return len + 1;
}
if (!visited.contains(target) && wordList.contains(target)) {
temp.add(target);
visited.add(target);
}
chs[i] = old;
}
}
}
beginSet = temp;
len++;
}
return 0;
}X. BFS
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
wordList.add(endWord);
Queue<String> queue = new LinkedList<String>();
queue.add(beginWord);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0; i < size; i++){
String cur = queue.remove();
if(cur.equals(endWord)){ return level + 1;}
for(int j = 0; j < cur.length(); j++){
char[] word = cur.toCharArray();
for(char ch = 'a'; ch < 'z'; ch++){
word[j] = ch;
String check = new String(word);
if(!check.equals(cur) && wordList.contains(check)){
queue.add(check);
wordList.remove(check);
}
}
}
}
level++;
}
return 0;
}https://linchicoding.wordpress.com/2014/10/13/leetcode-word-ladder/
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null || end == null || start.length() != end.length() || start.length() == 0)
return 0;
// A queue used for breadth-first search
Deque<String> queue = new ArrayDeque<String>();
queue.offer(start);
Set<String> visited = new HashSet<String>(); // Record the strings that have been visited
int depth = 1;
int nodesInCurrentLevel = 1, nodesInNextLevel = 0;
// A breadth-first search starting from "start"
while (queue.peek() != null) {
String current = queue.poll();
nodesInCurrentLevel--;
// Try each string that is one character away from the current one
for (int i = 0; i < current.length(); i++) {
char[] charCurrent = current.toCharArray();
for (char c = 'a'; c <= 'z'; c++) {
charCurrent[i] = c;
String temp = new String(charCurrent);
if (temp.equals(end)) // Reach target string with one more transformation
return depth+1;
if (!visited.contains(temp) && dict.contains(temp)) {
queue.offer(temp);
nodesInNextLevel++;
visited.add(temp);
}
}
}
// All nodes at the current level are done; prepare to go to the next level
if (nodesInCurrentLevel == 0) {
nodesInCurrentLevel = nodesInNextLevel;
nodesInNextLevel = 0;
depth++;
}
}
return 0;
}
EPI Java SOlution: Transform one string to another
TransformStringToOther.java
public static int transformString(Set<String> D, String s, String t) {
LinkedList<Pair<String, Integer>> q = new LinkedList<>();
D.remove(s); // Marks s as visited by erasing it in D.
q.push(new Pair<>(s, 0));
while (!q.isEmpty()) {
Pair<String, Integer> f = q.peek();
// Returns if we find a match.
if (f.getFirst().equals(t)) {
return f.getSecond(); // Number of steps reaches t.
}
// Tries all possible transformations of f.first.
String str = f.getFirst();
for (int i = 0; i < str.length(); ++i) {
String strStart = i == 0 ? "" : str.substring(0, i);
String strEnd = i + 1 < str.length() ? str.substring(i + 1) : "";
for (int j = 0; j < 26; ++j) { // Iterates through 'a' ~ 'z'.
String modStr = strStart + (char) ('a' + j) + strEnd;
if (D.remove(modStr)) {
q.push(new Pair<>(modStr, f.getSecond() + 1));
}
}
}
q.pop();
}
return -1; // Cannot find a possible transformations.
}
LeetCode – Word Ladder
https://leetcode.com/discuss/30872/short-java-bfs-solutionI modify the part of string concatenation and it runs with 476 ms
We can use two queues to traverse the tree, one stores the nodes, the other stores the step numbers. public int ladderLength(String start, String end, HashSet<String> dict) { if (dict.size() == 0) return 0; LinkedList<String> wordQueue = new LinkedList<String>(); LinkedList<Integer> distanceQueue = new LinkedList<Integer>(); wordQueue.add(start); distanceQueue.add(1); while(!wordQueue.isEmpty()){ String currWord = wordQueue.pop(); Integer currDistance = distanceQueue.pop(); if(currWord.equals(end)){ return currDistance; } for(int i=0; i<currWord.length(); i++){ char[] currCharArr = currWord.toCharArray(); for(char c='a'; c<='z'; c++){ currCharArr[i] = c; String newWord = new String(currCharArr); if(dict.contains(newWord)){ wordQueue.add(newWord); distanceQueue.add(currDistance+1); dict.remove(newWord); } } } } return 0; }https://leetcode.com/discuss/50930/java-solution-using-dijkstras-algorithm-with-explanation
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) { Set<String> reached = new HashSet<String>(); reached.add(beginWord); wordDict.add(endWord); int distance = 1; while(!reached.contains(endWord)) { Set<String> toAdd = new HashSet<String>(); for(String each : reached) { for (int i = 0; i < each.length(); i++) { char[] chars = each.toCharArray(); for (char ch = 'a'; ch <= 'z'; ch++) { chars[i] = ch; String word = new String(chars); if(wordDict.contains(word)) { toAdd.add(word); wordDict.remove(word); } } } } distance ++; if(toAdd.size() == 0) return 0; reached = toAdd; } return distance; }
https://linchicoding.wordpress.com/2014/10/13/leetcode-word-ladder/
- At first I was considering using recursion, which results in a “DFS” structure, and need to keep track of min steps, because it may already traverse down too far in one recursion then reach the end, yet in other branches may only need much fewer steps. This is an indication that we should use “BFS” instead.
ublic int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
Set<String> reached = new HashSet<String>();
reached.add(beginWord);
wordDict.add(endWord);
int distance = 1;
while(!reached.contains(endWord)) {
Set<String> toAdd = new HashSet<String>();
for(String each : reached) {
for (int i = 0; i < each.length(); i++) {
char[] chars = each.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
if(wordDict.contains(word)) {
toAdd.add(word);
wordDict.remove(word);
}
}
}
}
distance ++;
if(toAdd.size() == 0) return 0;
reached = toAdd;
}
return distance;
}
Basically I keep two sets of words, one set reached that represents the borders that have been reached with "distance" steps; another set wordDict that has not been reached. In the while loop, for each word in the reached set, I give all variations and check if it matches anything from wordDict, if it has a match, I add that word into toAdd set, which will be my "reached" set in the next loop, and remove the word from wordDict because I already reached it in this step. And at the end of while loop, I check the size of toAdd, which means that if I can't reach any new String from wordDict, I won't be able to reach the endWord, then just return 0. Finally if the endWord is in reached set, I return the current steps "distance".
The idea is that reached always contain only the ones we just reached in the last step, and wordDict always contain the ones that haven't been reached. This is pretty much what Dijkstra's algorithm does, or you can see this as some variation of BFS.
X. Two-End BFS
https://discuss.leetcode.com/topic/10372/share-my-two-end-bfs-in-c-80ms/9
https://leetcode.com/discuss/68935/two-end-bfs-in-java-31ms
Convert this problem to a math problem: Find a shortest path from one Vertex to another in a graph. Then searching from both Vertexes always visits less Vertexes than searching from one Vertex. But I can't prove this theory
using two ends by alternating beginSet and endSet
you are replacing a big search tree in the one-end solution with two smaller trees in the two-end solution. Both solutions have the same TOTAL depth, yet tree width grows exponentially w.r.t. depths, and the two-end solutions results in less nodes being visited.
Though simply remove target from wordList will be more efficient, but will modify original parameters. So I suggest using this HashSet to keep all visited is more suitable.
i think the intuition is that you are replacing a big search tree in the one-end solution with two smaller trees in the two-end solution. Both solutions have the same TOTAL depth, yet tree width grows exponentially w.r.t. depths, and the two-end solutions results in less nodes being visited.
i think the intuition is that you are replacing a big search tree in the one-end solution with two smaller trees in the two-end solution. Both solutions have the same TOTAL depth, yet tree width grows exponentially w.r.t. depths, and the two-end solutions results in less nodes being visited.
This is my code with some small modifications. Run time is 23ms.
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
int pathLength = 2;
Set<String> start = new HashSet<>();
Set<String> end = new HashSet<>();
start.add(beginWord);
end.add(endWord);
wordList.remove(beginWord);
wordList.remove(endWord);
while(!start.isEmpty()){
if(start.size() > end.size()){
Set<String> temp = start;
start = end;
end = temp;
}
Set<String> next = new HashSet<>();
for(String cur : start){
char[] strArray = cur.toCharArray();
for(int i = 0; i < strArray.length;i++){
char old = strArray[i];
for(char c = 'a';c <= 'z';c++){
strArray[i] = c;
String str = String.valueOf(strArray);
if(end.contains(str)){
return pathLength;
}
if(wordList.contains(str)){
next.add(str);
wordList.remove(str);
}
}
strArray[i] = old;
}
}
start = next;
pathLength++;
}
return 0;
}
Two further improvements.
- for (String word : set1) { dict.remove(word); }; can be replace by dict.removeAll(set1)
- char[] chars = str.toCharArray(); put it outside of second for loop can be faster(also need to record the original char and recover), since Java uses System.arraycopy to implement str.toCharArray() method. This can be N times faster. N is the length of word.
Two-End BFS recusion
https://discuss.leetcode.com/topic/17956/super-fast-java-solution-using-two-end-bfs
public int ladderLength(String start, String end, Set<String> dict) {
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
set1.add(start);
set2.add(end);
return helper(dict, set1, set2, 1);
}
int helper(Set<String> dict, Set<String> set1, Set<String> set2, int level) {
if (set1.isEmpty()) return 0;
if (set1.size() > set2.size()) return helper(dict, set2, set1, level);
// remove words from both ends
for (String word : set1) { dict.remove(word); };
for (String word : set2) { dict.remove(word); };
// the set for next level
Set<String> set = new HashSet<String>();
// for each string in the current level
for (String str : set1) {
for (int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();
// change letter at every position
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
// found the word in other end(set)
if (set2.contains(word)) {
return level + 1;
}
// if not, add to the next level
if (dict.contains(word)) {
set.add(word);
}
}
}
}
return helper(dict, set2, set, level + 1);
}
前几天和群友说起来，构图的时候，除去将每个字符依次从a替换至z，有没有进一步的优化。
当然是有……例如我有cap这个单词，创建三个key，*ap, c*p, ca*，然后将cap加入这三个key对应的list。依次对字典里所有单词做相同的事情。
两个不同的单词不可能同时分别出现在两个list中，（比如说单词A，单词B出现在 *ap中，单词A出现在c*p中，则单词B不可能出现在c*p中）。于是对于某个单词，比如说cap，只要连接*ap, c*p, ca*三个list，就可以得到它在图中所有的邻接节点
经验证速度比我的用a-z替换的code快一倍。当然，再进一步优化可以加上双向广搜。
X.
https://leetcode.com/discuss/433/keep-hitting-time-limit-exceeded-exception-word-ladder-java
X. Dijkstra
https://leetcode.com/discuss/20587/accepted-java-solution-based-on-dijkstras-algorithm
http://www.geeksforgeeks.org/length-of-shortest-chain-to-reach-a-target-word/
Read full article from LeetCode - Word Ladder | Darren's Blog
当然是有……例如我有cap这个单词，创建三个key，*ap, c*p, ca*，然后将cap加入这三个key对应的list。依次对字典里所有单词做相同的事情。
两个不同的单词不可能同时分别出现在两个list中，（比如说单词A，单词B出现在 *ap中，单词A出现在c*p中，则单词B不可能出现在c*p中）。于是对于某个单词，比如说cap，只要连接*ap, c*p, ca*三个list，就可以得到它在图中所有的邻接节点
经验证速度比我的用a-z替换的code快一倍。当然，再进一步优化可以加上双向广搜。
X.
https://leetcode.com/discuss/433/keep-hitting-time-limit-exceeded-exception-word-ladder-java
Seems you use
O(N^2) to build the graph, then find to shortest path from start string toend string. It is a solution, but not efficient.
You can do the BFS in this way, initialize the BFS queue with only one element
start string. Then go thru the BFS queue one by one, as we know the queue will increase during the BFS process. The way to expand the current string to see if it can generate another string in the dictionary and not appear in the BFS queue before. How to generate? Scan the characters in the string one by one, try to replace with other characters a to z.
If you do BFS in the way above, you do not have to touch all words in the dictionary to build graph. Considering the dictionary might be huge
public int ladderLength(String start, String end, HashSet<String> dict) {
//building a graph
dict.add(start);
dict.add(end);
int n = dict.size();
//the graph consisting nodes array
Node[] nodes= new Node[n];
Iterator itr = dict.iterator();
Node startNode=null, endNode=null;
//create node for each dict word
for (int i = 0; i < n; i++) {
Node nd = new Node();
nd.data = (String)itr.next();
nodes[i] = nd;
//set start and end
if(nd.data.equals(start))
startNode = nd;
if(nd.data.equals(end))
endNode = nd;
}
//O(n-square)
//find neighbors of each node
for (int i = 0; i < n; i++) {
Node current = nodes[i];
current.neighbor = neighbor(current,nodes);
}
//BFS implemented by a Queue
Queue<Node> aQ = new LinkedList<Node>();
aQ.add(startNode);
int counter = 1;
while(!aQ.isEmpty()){ //O(n-square) n is the # of edge
Node pointer = (Node)aQ.poll();
mark(pointer);
if(pointer==endNode){
return pointer.distance;
}
Iterator<Node> neiItr = pointer.neighbor.iterator();
while (neiItr.hasNext()) {
Node current = (Node)neiItr.next();
if(current.visited==false){
aQ.add(current);
current.distance = ++counter;
}
}
}
return 0;
}
public void mark(Node t){
t.visited=true;
}
public void markAll(ArrayList<Node> t){
Iterator itr = t.iterator();
while(itr.hasNext()){
((Node)itr.next()).visited=true;
}
}
public ArrayList<Node> neighbor(Node nd, Node[] nodes){
ArrayList<Node> neighors = new ArrayList<Node>();
for (int i = 0; i < nodes.length; i++) {
Node current = nodes[i];
if(current.isNeighborOf(nd))
neighors.add(current);
}
return neighors;
}
class Node{
String data;
int distance = 0;
boolean visited = false;
ArrayList<Node> neighbor;
/**
* O(n)
* @param t
* @return
*/
public boolean isNeighborOf(Node t){
int ctr = 0;
for (int i = 0; i < data.length(); i++) {
if(data.charAt(i)!=t.data.charAt(i)){
ctr++;
if(ctr>1)
return false;
}
}
//ctr has to be bigger than 1
//set is non duplicate
return true;
}
}X. Dijkstra
https://leetcode.com/discuss/20587/accepted-java-solution-based-on-dijkstras-algorithm
why you like to use Dijkstra in an unweighted graph?
if weight is 1, you can just use breadth first search.
public int ladderLength(String start, String end, Set<String> dict) {
// Init vertices
WordVertex startVertex = new WordVertex(start);
WordVertex endVertex = new WordVertex(end);
startVertex.dist = 0;
List<WordVertex> vertices = new ArrayList<WordVertex>();
vertices.add(startVertex);
vertices.add(endVertex);
for (String word:dict) {
vertices.add(new WordVertex(word));
}
// Construct graph
for(int i=0; i<vertices.size(); i++) {
WordVertex vertex = vertices.get(i);
for(int j=i+1; j<vertices.size(); j++) {
WordVertex neighbor = vertices.get(j);
int diff = 0;
for (int k=0; k<vertex.word.length(); k++) {
if (vertex.word.charAt(k) != neighbor.word.charAt(k) && diff++ == 1) {
break;
}
}
if (diff == 1) {
vertex.neighbors.add(neighbor);
neighbor.neighbors.add(vertex);
}
}
}
// Find shortest path. Dijkstra's algorithm.
PriorityQueue<WordVertex> queue = new PriorityQueue<WordVertex>();
for (WordVertex v:vertices) {
queue.add(v);
}
while(!queue.isEmpty()) {
WordVertex v = queue.poll();
if (v.dist == Integer.MAX_VALUE) continue;
for (WordVertex n:v.neighbors) {
if (!n.visited) {
if (v.dist + 1 < n.dist) {
n.dist = v.dist + 1;
queue.remove(n);
queue.add(n);
}
}
}
v.visited = true;
}
return endVertex.dist == Integer.MAX_VALUE ? 0 : endVertex.dist + 1;
}
// To check if strings differ by exactly one characterbool isadjacent(string& a, string& b){ int count = 0; // to store count of differences int n = a.length(); // Iterate through all characters and return false // if there are more than one mismatching characters for (int i = 0; i < n; i++) { if (a[i] != b[i]) count++; if (count > 1) return false; } return count == 1 ? true : false;}// A queue item to store word and minimum chain length// to reach the word.struct QItem{ string word; int len;};// Returns length of shortest chain to reach 'target' from 'start'// using minimum number of adjacent moves. D is dictionaryint shortestChainLen(string& start, string& target, set<string> &D){ // Create a queue for BFS and insert 'start' as source vertex queue<QItem> Q; QItem item = {start, 1}; // Chain length for start word is 1 Q.push(item); // While queue is not empty while (!Q.empty()) { // Take the front word QItem curr = Q.front(); Q.pop(); // Go through all words of dictionary for (typeof(D.begin()) it = D.begin(); it != D.end(); it++) { // Process a dictionary word if it is adjacent to current // word (or vertex) of BFS string temp = *it; if (isadjacent(curr.word, temp)) { // Add the dictionary word to Q item.word = temp; item.len = curr.len + 1; Q.push(item); // Remove from dictionary so that this word is not // processed again. This is like marking visited D.erase(temp); // If we reached target if (temp == target) return item.len; } } } return 0;}