leetcode-WordLadder

2016-07-26 21:09:00

题目：
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 intermediate word must exist in the word list
For example,

Given:

beginWord = "hit"endWord = "cog"wordList = ["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.

由于只需要求最短的距离，所以直接BFS就行了。这题OJ的数据卡得比较严，裸BFS会TLE。没有必要写双向的BFS，注意下剪枝就可以了。直接放代码。
code:

import java.util.*;public class WordLadder {    public int ladderLength(String beginWord, String endWord, Set wordList) {        HashMap map = new HashMap();        LinkedList queue = new LinkedList();        queue.offer(beginWord);        map.put(beginWord, 1);        boolean flag = false;        while(!queue.isEmpty()){            String curr = queue.poll();            for(String next : getNextWords(curr, wordList)){                if(next.equals(endWord)){                    flag = true;                    map.put(next, map.get(curr) + 1);                    System.out.println(next + " " + map.get(next));                    return map.get(next);                }                if(wordList.contains(next)){                    if(!map.containsKey(next)){                        map.put(next, map.get(curr) + 1);                        System.out.println(next + " " + map.get(next));                        queue.offer(next);                    }                }            }        }        if(flag) return map.get(endWord);        else return 0;    }    public List getNextWords(String word, Set wordList){        List nextWords = new ArrayList();        for(int i = 0; i  wordList = new HashSet();        wordList.add("a");        wordList.add("b");        wordList.add("c");        String beginWord = "a";        String endWord = "c";        int result = WL.ladderLength(beginWord, endWord, wordList);        System.out.println(result);    }}

关键字：产品经理

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！