【LeetCode】Word Ladder 字符串

题目：Word Ladder

/**LeetCode word ladder * 题目：给定一个起始单词和一个终结单词以及一个字典，要求每次变换一个字符，成为字典中新的词，直到变为最后的词，要求其最短路径 * 思路：利用队列，先弹出第一个词，分别将词中每一个字符替换直到找到一个字典中存在的词，加入队列，直到匹配的词是最后一个，此时终止 * 如果没有这样的路径，则返回0 */package javaTrain;import java.util.LinkedList;import java.util.Set;public class Train21 {public int ladderLength(String start, String end, Set<String> dict) {if(dict.size() == 0) return 0;LinkedList<String> queue = new LinkedList();String tag = new String();queue.add(start);queue.add(tag);int len = 1;while(queue.size() > 1){String top = queue.pop();if(top == tag){//标志着对于一个词的每个字符的替换测试已经结束，，有用的都放在队列后面了len++;queue.add(tag);continue;}else if(top == end){return len;}for(int i = 0;i < top.length();i++){char[] zifu = top.toCharArray();for(char c = 'a';c <= 'z';c++){zifu[i] = c;String newWord = new String(zifu);if(dict.contains(newWord)){queue.add(newWord);}dict.remove(newWord);}}} return 0;

}}

自己变得跟水晶一般透明，

相关文章：

你感兴趣的文章：

标签云：