`
huntfor
  • 浏览: 201579 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Word Ladder

 
阅读更多

Word Ladder

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, 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.

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

 这道题是考察图的遍历,一般而言,图的遍历跟树的遍历相似,同样为DFS和BFS,但是DFS因为使用递归,所以对规模较大的数据量比较容易超时,尤其对于这种求层数的题。

该题是典型的求层数类型。考虑使用BFS。感兴趣的可以考虑用DFS,我觉得不用试,肯定超时。

我对图不太熟悉,本以为要构建图的数据结构,后来想了一下,貌似又不用,只需要判断一下是否邻接即可。

第一个版本的代码是酱紫的:

public int ladderLength(String start, String end, Set<String> dict) {
    	Set<String> set = new HashSet<String>(dict);
    	Map<String,Boolean> map = new HashMap<String,Boolean>();
    	set.add(start);
    	set.add(end);
    	for(String s : set){
    		map.put(s, false);
    	}
    	Queue<String> queue = new ArrayDeque<String>();
    	Queue<String> temQ = new ArrayDeque<String>();
    	queue.offer(start);
    	map.put(start, true);
    	int level = 0;
    	while(!queue.isEmpty()){
    		String str = queue.poll();
    		for(String s : set){
    			if(!map.get(s) && match(str, s)){
    				temQ.offer(s);
    				if(s.equals(end)){
    					return level + 2;
    				}
    			}
    		}
    		if(queue.isEmpty()){
    			queue.addAll(temQ);
    			temQ.clear();
    			level++;
    		}
    	}
    	return 0;
    }
    private boolean match(String str1,String str2){
    	int notMatch = 0;
    	for(int i = 0 ; i < str1.length(); i++){
    		if(str1.charAt(i) != str2.charAt(i)){
    			notMatch++;
    			if(notMatch > 1){
    				return false;
    			}
    		}
    	}
    	return true; 
    }

 这里要对遍历过的点进行标记,不熟悉的可以看这里。这里我对是否邻接用了match方法对每一个set集合中的字符串进行判断,但是对于规模较大的数据还是超时了,后来看了其他人的方法,不需要判断集合中的字符串是否match,反过来判断match的字符串是否在集合中。这样对于大规模的集合就可以达到时间优化的目的,但是对于小集合反而多余判断太多。不过好歹也是O(str.length())的时间复杂度,不大。因此就采用了这种方法,代码如下:

 public int ladderLength(String start, String end, Set<String> dict) {
    	Set<String> set = new HashSet<String>(dict);
    	Map<String,Boolean> map = new HashMap<String,Boolean>();
    	set.add(start);
    	set.add(end);
    	for(String s : set){
    		map.put(s, false);
    	}
    	Queue<String> queue = new ArrayDeque<String>();
    	Queue<String> temQ = new ArrayDeque<String>();
    	queue.offer(start);
    	map.put(start, true);
    	int level = 0;
    	while(!queue.isEmpty()){
    		String str = queue.poll();
    		for(int i = 0 ; i < str.length(); i++){
    			for(int j = 0; j < 26; j++){
    				char[] copyStr = str.toCharArray();
    				copyStr[i] =(char) ('a' + j);
    				String s = new String(copyStr);
    				if(set.contains(s) && !map.get(s) ){
    					temQ.offer(s);
    					map.put(s, true);
    					if(end.equals(s)){
    						return level + 2;
    					}
    				}
    			}
    		}
    		if(queue.isEmpty()){
    			queue.addAll(temQ);
    			temQ.clear();
    			level++;
    		}
    	}
    	return 0;
    }

 

 

 

分享到:
评论

相关推荐

    126.Word Ladder II 词语阶梯二【LeetCode单题讲解系列】

    126.Word_Ladder_II_词语阶梯二【LeetCode单题讲解系列】

    python-leetcode题解之127-Word-Ladder

    python python_leetcode题解之127_Word_Ladder

    python-leetcode题解之126-Word-Ladder-II

    python python_leetcode题解之126_Word_Ladder_II

    js-leetcode题解之127-word-ladder.js

    javascript js_leetcode题解之127-word-ladder.js

    word ladder

    经典字梯游戏c++代码,经测试通过的哦,leetcode上面的题目

    js-leetcode题解之126-word-ladder-ii.js

    javascript js_leetcode题解之126-word-ladder-ii.js

    LeetCode题解(java语言实现).pdf

    * Word Ladder:该题目要求将一个单词转换成另一个单词,实现方法使用了广度优先搜索算法。 二、树和图 * Median of Two Sorted Arrays Java:该题目要求找到两个排序数组的中位数,实现方法使用了二分查找算法。 ...

    leetcode刷题LeetCode1500道单词接龙Python3

    在LeetCode上,单词接龙类问题可能表现为“Anagrams”(同字母异序词)或者“Word Ladder”(单词阶梯),这些题目要求高效地搜索满足条件的单词序列。 【压缩包子文件的文件名称列表】"LeetCode-main"可能包含了一...

    leetcode多少题-word_ladder:字梯

    leetcode 多少题带有堆栈和队列的字梯 您将针对 Lewis Carroll ...在本作业中,您将实现一个函数word_ladder来生成这些字梯。 有许多可能的算法来生成字梯,但一个简单的算法使用堆栈和队列的组合,如

    leetcode1-240题中文题解,md格式,java

    1. leetCode-126-Word-LadderII.md:这涉及到第126题,词梯问题,通常是一个字符串转换问题,目标是找到两个单词之间的最短转换序列,每次只改变一个字母。 2. leetcode-224-Basic-Calculator.md:这是第224题,基础...

    LeetCode题解 - Java语言实现-181页.pdf

    6. Word Ladder 单词梯是一个字符串问题,要求将一个单词转换为另一个单词,并且每次转换只能改变一个字符。可以使用广度优先搜索或深度优先搜索来解决该问题。 7. Median of Two Sorted Arrays in Java 两个排序...

    Amazon亚麻 最新leetcode tag题

    5. **搜索和回溯**:对于“NumberofIslands”、“WordLadder”等题目,应聘者必须运用搜索算法,如广度优先搜索(BFS)、深度优先搜索(DFS)以及回溯算法来寻找解决方案。 6. **动态规划和贪心算法**:...

    leetcode316-LeetCode:leetcode的解决方案

    leetcode 316 LeetCode Summary Exclusive Time of Functions: 栈 Friend Circles:DFS Print Binary Tree:二叉树 Maximal Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:...

    leetcode代码200题c++

    8. **Word Ladder II**:这是一个词链问题,涉及到广度优先搜索和回溯法,寻找从一个单词转换到另一个单词的最短路径。 9. **Regular Expression Matching**:这个涉及到字符串匹配和动态规划。实现一个函数来判断...

    LeetCode解题总结

    9.1 单词变换路径(Word Ladder) 9.1.1 是否存在变换路径 9.1.2 所有最短变换路径9.2 包围区域 10. 深度优先搜索 10.1 N皇后问题 10.2 恢复IP地址 10.3 集合元素之和 10.3.1 元素可以重复 10.3.2 元素不可重复 ...

    Coding Interview In Java

    5 Word Ladder 27 6 Word Ladder II 29 7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 ...

    leetcode-python:python中的leetcode

    力扣 Python 解决方案Leetcode 是准备技术编码面试的...特别案例: Word Ladder II,我的 AC 代码比这个 repo 中的代码慢得多。 但是这个 repo 中的一个得到了 TLE,不知道为什么。 任何想法都将受到高度赞赏。 谢谢!

    Leetcode代码以及解答(2)

    Word Ladder **知识点:** - **问题描述:** - 找到由开始到结尾的字符串的转换字符串集合,中间的转换字符串都要在给定的列表中,并且每一步只能改变一个字符。 - **解决方案分析:** - **原始方法:** - ...

    java-leetcode-solutions:一些LeetCode问题的解决方案

    例如,`WordLadder.java`可能涉及到词链问题,需要理解图的邻接矩阵或邻接表表示。 6. **字符串处理**:如模式匹配、字符串反转、最长公共前缀等。`ValidPalindrome.java`可能涉及字符串的比较和操作。 7. **位...

    javalruleetcode-leetcode:更多信息请访问Gitbook:https://wentao-shao.gitbook.io/

    java lru leetcode ...Ladder Add Two Numbers Matrix Spiral Matrix Mergesort [Algorithm Swap](Mergesort/Algorithm swap.md) Numbers Queue Stack Toposort Trie Tree Two Pointers Union Find

Global site tag (gtag.js) - Google Analytics