Java for LeetCode 127 Word Ladder

Given two words (beginWord and endWord), and a dictionary, 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 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.

解题思路一：

对set进行逐个遍历，递归实现，JAVA实现如下：

	static public int ladderLength(String beginWord, String endWord,

			Set<String> wordDict) {

		int result = wordDict.size() + 2;

		Set<String> set = new HashSet<String>(wordDict);

		if (oneStep(beginWord, endWord))

			return 2;

		for (String s : wordDict) {

			if (oneStep(beginWord, s)) {

				set.remove(s);

				int temp = ladderLength(s, endWord, set);

				if (temp != 0)

					result = Math.min(result, temp + 1);

				set.add(s);

			}

		}

		if (result == wordDict.size() + 2)

			return 0;

		return result;

	}

	public static boolean oneStep(String s1, String s2) {

		int res = 0;

		for (int i = 0; i < s1.length(); i++)

			if (s1.charAt(i) != s2.charAt(i))

				res++;

		return res == 1;

	}

结果TLE

解题思路二：

发现直接遍历是行不通的，实际上如果使用了oneStep函数，不管怎么弄都会TLE的(貌似在C++中可以AC)。

本题的做法应该是采用图的BFS来做，同时oneStep的匹配也比较有意思，JAVA实现如下：

static public int ladderLength(String start, String end, Set<String> dict) {

        HashMap<String, Integer> disMap = new HashMap<String, Integer>();

        LinkedList<String> queue = new LinkedList<String>();

        queue.add(start);

        disMap.put(start, 1);

        while (!queue.isEmpty()) {

            String word = queue.poll();

            for (int i = 0; i < word.length(); i++) {

                for (char ch = 'a'; ch <= 'z'; ch++) {

                    StringBuilder sb = new StringBuilder(word);

                    sb.setCharAt(i, ch);

                    String nextWord = sb.toString();

                    if (end.equals(nextWord))

                        return disMap.get(word) + 1;

                    if (dict.contains(nextWord) && !disMap.containsKey(nextWord)) {

                        disMap.put(nextWord, disMap.get(word) + 1);

                        queue.add(nextWord);

                    }

                }

            }

        }

        return 0;

    }

巴特西

Java for LeetCode 127 Word Ladder

最新文章

热门文章