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. 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.
- find shortest path: using bfs , check layer by layer (expanding)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//find shortest length of path
//using bfs -> expand layer by layer and using Queue
LinkedList<String> q = new LinkedList<String>();
q.push(beginWord);
HashSet<String> set = new HashSet<>(wordList);
if(!set.contains(endWord)) return 0;
if(set.contains(beginWord)) set.remove(beginWord);//why move this
int step = 0;
while(!q.isEmpty()){
//check each layer
++step;
for(int k = q.size(); k>0; k--){
String cur = q.pop();
//expand next layer and check if it hits the success
char[] curArr = cur.toCharArray();
//change one character
for(int i = 0; i<cur.length(); i++){
char a = curArr[i];
for(char j = 'a'; j <= 'z'; j++){
curArr[i] = j; //ai
//System.out.println(String.valueOf(curArr));
if(String.valueOf(curArr).equals(endWord)) return step+1;
if(set.contains(String.valueOf(curArr))){
q.add(String.valueOf(curArr));
set.remove(String.valueOf(curArr));//move this for ad them into array again
}
}
curArr[i] = a;
}
}
}
return 0;
}
}- here I did not come up other solution when I implement getStrWithOneDistance()
- I use HashSet and Arraylist to get the one distance string
- Instead we can use alphbet 26 words
import java.io.*;
import java.util.*;
class Solution {
static int shortestWordEditPath(String source, String target, String[] words) {
//bfs
//time: O(M*M*N) 26* M*N (words*length of word) * M(time to create substring)
HashSet<String> set = new HashSet<>();
for(String str : words){
set.add(str);
}
if(!set.contains(target)) return -1;
Queue<String> q = new LinkedList<>();
q.add(source);
int steps = 0;
while(!q.isEmpty()){
int size = q.size();
steps++;
for(int i=0 ; i<size ; i++){
String cur = q.poll();
boolean[] success = new boolean[1];
ArrayList<String> strWithOneDistance = getStrWithOneDistance(cur, set, success, target);
//System.out.println(steps);
for(String str : strWithOneDistance){
//System.out.print(str+" ");
q.offer(str);
}
//System.out.println();
if(success[0]==true){
return steps;
}
}
}
//check -1 case
return -1;
}
//add 1 distance string and return it.
static ArrayList<String> getStrWithOneDistance(String cur, HashSet<String> set, boolean[] success, String target){
ArrayList<String> res = new ArrayList<>();
for(String str : set){
if(dist(str, cur)==1){
res.add(str);
if(str.equals(target)){
success[0] = true;
}
}
}
for(String str : res){
if(set.contains(str)) set.remove(str);
}
return res;
}
static int dist(String str1, String str2){
if(str1.length()!=str2.length()) return -1;
int res = 0;
for(int i = 0; i<str1.length(); i++){
if(str1.charAt(i)!=str2.charAt(i)) res++;
}
return res;
}
public static void main(String[] args) {
}
}
-- (reference pramp)[https://www.pramp.com/challenge/MW75pP53wAtzNPVLPG0d]