Description

LeetCode 127

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:

  1. Only one letter can be changed at a time.
  2. 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.

Analysis

The is a typical BFS problem. Talking about brute-force searching algorithms, we have two methods, BFS and DFS. Although they are both brute-force algorithms and their worst-case time are same, their efficiency can be different because of pruning.

DFS is usually implemented as backtracking. If we want to find one specific condition or list all the conditions, we should use DFS. When we find a specific condition we could stop the searching process. And for listing all the conditions, DFS does not need a queue to store the states. It saves more space than BFS.

However, if we want to find the minimum step to one state, using BFS is a better choice. We could extend the element by one integer that records the layer number. And use one queue to store the elements as the states. Then extend the states one layer by one layer.

In this problem, we can start from the end word and extend it until finding the begin word. And the used states could be erased from the list because the result is the only thing we want and the middle states are not important.

Solution

class Item{
    public String str;
    public int index;
    public Item(String s,int i){
        str=s;
        index=i;
    }
}
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int index=wordList.indexOf(endWord);
        if(index==-1) return 0;
        Queue<Item> q=new LinkedList<>();
        q.add(new Item(endWord,1));
        wordList.remove(endWord);
        int qsize=1;
        Item temp;
        while(q.size()>0)
        {
            qsize=q.size();
            for(int j=0;j<qsize;j++)
            {
                temp=q.poll();
                if(dis(temp.str,beginWord)==1)
                {
                    return temp.index+1;
                }
                for(int i=0;i<wordList.size();i++)
                {
                    if(dis(wordList.get(i),temp.str)==1)
                    {
                        q.add(new Item(wordList.get(i),temp.index+1));
                        wordList.remove(wordList.get(i));
                    }
                }
            }
        }
        return 0;
    }
    public int dis(String word1,String word2)
    {
        int s=0;
        for(int i=0;i<word1.length();i++)
        {
            if(word1.charAt(i)!=word2.charAt(i))
                s++;
        }
        return s;
    }
}

Reference

[1] https://www.geeksforgeeks.org/word-ladder-length-of-shortest-chain-to-reach-a-target-word/

[2] https://www.jiuzhang.com/qa/623/

 

 

 

1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *