Tadowの自留地
文章 标签 分类 关于 SelfHost
Tadowの自留地

目录

一道 LeetCode 引发的惨案

reso1mi 收录于 算法
   约 1738 字   预计阅读 4 分钟 

一道 LeetCode 搜索题引发的惨案

1. 先上 题目

给定两个单词（_beginWord _和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。 原题链接

https://imlgwpicture.oss-cn-qingdao.aliyuncs.com/blogImage/3V6EQ77R_%28%292SCR%248R%5B%245F7.png

其实这题明显是 BFS（广搜） 题目类型也说了是广搜，但是我不信邪写了 DFS（毕竟代码比较好写），然后惨案就发生了。

   // 标记数组
	// 默认都是 0
	private static int[] mark;

	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		// 不存在
		mark = new int[wordList.size() + 1];
		if (!wordList.contains(endWord)) {
			return 0;
		}
		// dfs 开始
		dfs(beginWord, endWord, wordList);
		// 无法转换
		if (min == Integer.MAX_VALUE) {
			return 0;
		}
		return min + 1;
	}

	int min = Integer.MAX_VALUE;

	// dfs
	private void dfs(String beginWord, String endWord, List<String> wordList) {
		//当相等的时候
		if (beginWord.equals(endWord)) {
			int step = 0;
			for (int i = 0; i < mark.length; i++) {
				if (mark[i] == 1) {
					step++;
				}
			}
			//更新最小值
			min = step < min ? step : min;
			return;
		}
		for (int i = 0; i < wordList.size(); i++) {
			if (mark[i] == 0 && cmp(beginWord, wordList.get(i))) {
				mark[i] = 1;
				dfs(wordList.get(i), endWord, wordList);
				mark[i] = 0;
			}
		}
		return;
	}

	// 写一个函数判段是否只变化了一个字母
	private boolean cmp(String s1, String s2) {
		int count = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				count++;
			}
		}
		return count == 1;
	}

结果直接 TLE 了，后来想了想 DFS 每次都会尝试所有情况，而给的例子后面的数据量也比较大，而且这题是要统计最短路径，要全部递归完才能确定最小值，我把数据拿来自己测试跑了好长时间都没跑出来，而 BFS 没有递归只是会耗费的空间会比较大。从这里也可以总结出来 DFS 跟适合判断是否存在是否可达之类的问题，BFS 更适合做找最短最小之类的问题。上 BFS 代码

// 标记数组
	// 默认都是 0
	private static int[] mark;
	// 模拟队列
	class Que {
		String word;
		int step;
	}
	//BFS
	public int ladderLengthBFS(String beginWord, String endWord, List<String> wordList){
        // 不存在
		mark = new int[wordList.size() + 1];
		if (!wordList.contains(endWord)) {
			return 0;
		}
		// BFS
		int head = 0, tail = 0;
		// 初始化队列
		Que[] que = new Que[wordList.size() + 1];
		// 循环促使话述祖
		for (int i = 0; i < que.length; i++) {
			que[i] = new Que();
		}
		que[tail].word = beginWord;
		que[tail].step = 1;
		tail++;
		int flag=0;
		while (head < tail) {
			// 遍历字典
			for (int i = 0; i < wordList.size(); i++) {
				if (mark[i] == 0 && cmp(wordList.get(i), que[head].word)) {
					que[tail].word = wordList.get(i);
					//这里是从 head 开始的，所以应该是 head 的步数+1
					que[tail].step=que[head].step+1;
					// 标记为已经走过
					mark[i] = 1;
				   if (que[tail].word.equals(endWord)) {
					//到这里说明已经到终点了，而且是最短的，之后的最多就是相等
					//跳出循环
                       flag=1;
                       break;
			    	}
                    tail++;
				}
				
			}
            if(flag==1){
                break;
            }
			// 每次检查完一个单词就将其出队列
			head++;
		}
		return que[tail].step;
    }

	// 写一个函数判段没吃是否只变化了一个字母
	private boolean cmp(String s1, String s2) {
		int count = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				count++;
			}
		}
		return count == 1;
	}

PS：刚刚修改了下代码，我也佩服自己 BFS 都还没搞清楚就直接上了代码，然后结果居然还是对的，之前在 if 判断队尾元素是不是和 endWord 相等后还维护了一个最小值 min，后来想了想不对，最后一个和 endWord 相等的元素已经进栈了，已经是最短的了，后面的即使可以转换到也最多只能和当前的相等了。 如果只是为了统计最小值就可以直接 break 了。那如果不仅仅要统计最小值还要记录路径要怎么搞？

2. 加强版 单词接龙 2

是一道困难等级的题，需要在上面的基础上找出所有的最短的路径。

// 内部类
	class Que {
		String word;
		int step;
		Que prev;
		public String toString(){
			return (word + ":" + step);
		}		 
	}

	//返回值
	private  List<List<String>> res=new ArrayList<>();

	
	//BFS
	public List<List<String>> ladderLengthBFS(String beginWord, String endWord, List<String> wordList){
        //返回值
		//List<List<String>> res=new ArrayList<>();
		
        // 不存在
		mark = new int[wordList.size() + 1];
		if (!wordList.contains(endWord)) {
			return res;
		}
		// BFS
		int head = 0, tail = 0;
		// 初始化队列
		Que[] que = new Que[wordList.size() + 1];
		// 循环促使话述祖
		for (int i = 0; i < que.length; i++) {
			que[i] = new Que();
		}
		//先把第一个单词放进去
		que[tail].word = beginWord;
		que[tail].step = 1;
		tail++;
		List<Que> quelist=new ArrayList<>();
		while (head < tail) {
			// 遍历字典
			for (int i = 0; i < wordList.size(); i++) {
				if (mark[i] == 0 && cmp(wordList.get(i), que[head].word)) {
					que[tail].word = wordList.get(i);
					//这里是从 head 开始的，所以应该是 head 的步数+1
					que[tail].step=que[head].step+1;
					//que[head].next=que[tail];
					// 标记为已经走过
					mark[i] = 1;
				   if (que[tail].word.equals(endWord)) {	
				   		//记录最小值
				   		min=que[tail].step;
				   		//到这里队列后面就不用再插入元素了

				   		//2. 把之前走过的路在下一个 head

				   		//将队列变成 list
				   		for(int j=0;j<=tail;j++){
				   			quelist.add(que[j]);
				   		}
				   		markDfs= new int[wordList.size() + 1]; 
				   		// 1. 用 DFS 试一下
				   		dfsBfs(que[0],endWord,quelist);
			    	}
                    tail++;
				}
			}
			// 每次检查完一个单词就将其出队列
			head++;
		}
		return res;
    }

    private void dfsBfs(Que beginWord,String endWord,List<Que> ques){
    	int step = 0;
		for (int i = 0; i < markDfs.length; i++) {
				if (markDfs[i] == 1) {
					step++;
				}
		}
		if(step>=min) return;
		if(step+1==min&&endWord.equals(beginWord.word)){
			List<String> list=new ArrayList<>();
			Stack<String> stack=new Stack<>();
			System.out.println(beginWord.word+":"+step);
			Que temp=beginWord;
				//找到一条
				for(int i=0;i<min;i++){
					stack.push(temp.word);
					System.out.print(temp.word+"<--");
					temp=temp.prev;
				}
				System.out.println();
				for(int i=0;i<min;i++){
					list.add(stack.pop());
				}
				res.add(list);
				System.out.println(res);
			return;
		}

		
		for (int i = 0; i < ques.size(); i++) {
			if (markDfs[i] == 0 && cmp(beginWord.word,ques.get(i).word)){
				markDfs[i] = 1;
				//连接两个节点
				//beginWord.next=ques.get(i);
				ques.get(i).prev=beginWord;
				dfsBfs(ques.get(i), endWord, ques);
				markDfs[i] = 0;
			}
		}
		return;
    }

	// private int step = 0;
	int min = Integer.MAX_VALUE;

	// 写一个函数判段没吃是否只变化了一个字母
	private boolean cmp(String s1, String s2) {
		int count = 0;
		for (int i = 0; i < s1.length(); i++) {
			if (s1.charAt(i) != s2.charAt(i)) {
				count++;
			}
		}
		return count == 1;
	}

整体上在 Que 上增加了一个 prev 的指针，遍历路径，一开始是用的 BFS 不过我想的太简单了，我只是把最后一个节点出队列然后再 BFS，后来发现不行（居然还跑过了 24 个测试案例），实际上这题我还是没有做出来，但是上面的方法应该是没问题的就是会 TLE😭，大概思路就是先 BFS 缩短 DFS 需要遍历的字典然后控制每次递归的身体不能超过 BFS 的到的最短路径 https://imlgwpicture.oss-cn-qingdao.aliyuncs.com/blogImage/blog.PNG 一开始只能跑几个数据的，优化下能跑几十个的，但是还是太慢了，毕竟是一道难题等以后学了相关的东西再来试试看能不能做出来吧。

算法，学着挺有意思，就是头有点凉。

更新于 2018-10-31
 数据结构, 算法, 搜索
返回 | 主页