127. Word Ladder

Que: A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s<sub>1</sub> -> s<sub>2</sub> -> ... -> s<sub>k</sub> such that:

• Every adjacent pair of words differs by a single letter.

• Every s<sub>i</sub> for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

• s<sub>k</sub> == 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.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation sequence is "hit" -> "hot" -> "dot" -> "dog" -> cog", which is 5 words long.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no valid transformation sequence.

Solution:

class Solution {
    class Pair{
        String str;
        int val;
        Pair(String _str,int _val){
            this.str = _str;
            this.val = _val;
        }
    }

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
          Set<String> st = new HashSet<String>();
          for(String str: wordList){  st.add(str); }
          Queue<Pair> q = new LinkedList<>();
          q.offer(new Pair(beginWord,1));
          while(!q.isEmpty()){
            String str = q.peek().str;
            int val = q.peek().val;
            q.poll();
            if(str.equals(endWord)){ return val; }
            for(int i=0;i<str.length();i++){
                char[] word = str.toCharArray();
                for(char ch='a';ch<='z';ch++){
                    word[i]=ch;
                    String tmp = new String(word);
                    if(st.contains(tmp)){
                        q.offer(new Pair(tmp,val+1));
                        st.remove(tmp);
                    }
                }
            }
          }
          return 0;
    }
}