Search

Word Ladder

Given two words beginWord and endWord, and a dictionary wordList, return the length of the 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.

Return 0 if there is no such transformation sequence.

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. 
 

Constraints:

  • 1 <= beginWord.length <= 100

  • endWord.length == beginWord.length

  • 1 <= wordList.length <= 5000

  • wordList[i].length == beginWord.length

  • beginWord, endWord, and wordList[i] consist of lowercase English letters.

  • beginWord != endWord

  • All the strings in wordList are unique.


Solution:


class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<String>();
        Set<String> words = new HashSet<>(wordList);
        words.remove(beginWord);
        queue.add(beginWord);
        
        int level = 0;
        while(!queue.isEmpty()){
        int size = queue.size();
        level++;
        for(int i=0;i<size;i++)
        {
            String currentword = queue.poll();
            if(currentword.equals(endWord)) return level;
            List<String> neighbors = neighbor(currentword);
            
            for(String neigh:neighbors)
            {
                if(words.contains(neigh))
                {
                    words.remove(neigh);
                    queue.add(neigh);
                }
            }
        }
        }
      return 0;  
    }
    
    public List<String> neighbor(String s)
    {
        char[] chars = s.toCharArray();
        List<String> result = new ArrayList<>();
        for(int i=0;i<chars.length;i++)
        {
            char temp=chars[i];
            for(char c='a';c<='z';c++)
            {
                chars[i]=c;
                String neighbor = new String(chars);
                result.add(neighbor);
            }
            chars[i]=temp;
        }
        return result;
    }
    
}



18 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.