首页 > 代码库 > Word Ladder

Word Ladder

2024-07-21 22:06:00   219人阅读

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence fromstart to end, such that:

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:

  • Return 0 if there is no such transformation sequence.
  • All words have the same length.
  • All words contain only lowercase alphabetic characters.

答案

public class Solution {
   public int ladderLength(String start, String end, Set<String> dict) {
        if(dict==null||dict.size()==0)
        {
            return 0;
        }
        if(!dict.contains(start)||!dict.contains(end))
        {
            return 0;
        }
        if(start==end)
        {
            return 1;
        }
        LinkedList<String> queue=new LinkedList<String>();
        Set<String> visited=new HashSet<String>(dict.size()*2);
        Map<String,Integer> len=new HashMap<String,Integer>(dict.size()*2);
        queue.add(start);
        visited.add(start);
        len.put(start,1);
        for(String p=queue.poll();p!=null;p=queue.poll())
        {
            int LEN=len.get(p);
            for(int i=0;i<p.length();i++)
            {
                StringBuilder builder=new StringBuilder(p);
                for(char c='a';c<='z';c++)
                {
                    builder.setCharAt(i,c);
                    String dest=builder.toString();
                    if(dict.contains(dest)&&!visited.contains(dest))
                    {
                        visited.add(dest);
                        queue.add(dest);
                        len.put(dest,LEN+1);
                        if(dest.equals(end))
                        {
                            return LEN+1;
                        }
                    }
                }
            }
        }
        return 0;
    }
}


Word Ladder


联系
我们