【LeetCode题解】127. 单词接龙

57 阅读 0 评论 38 点赞

我是靠谱客的博主爱听歌睫毛，最近开发中收集的这篇文章主要介绍【LeetCode题解】127. 单词接龙，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

version1：深度递归回溯超时

version2：不递归回溯如何遍历所有可能结果？层次遍历

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

每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:如果不存在这样的转换序列，返回 0。所有单词具有相同的长度。所有单词只由小写字母组成。字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:输入:
beginWord = "hit",endWord = "cog",wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
返回它的长度 5。
示例 2:输入:
beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]

输出: 0解释: endWord "cog" 不在字典中，所以无法进行转换。

version1：深度递归回溯超时

1、对List中每个元素判断是否能与beginWord一步转换，如果可以，则递归进行判断List中每个元素判断是否能与List.get(i)一步转换，如无法转换则回溯

2、isUsed数组标记以及加入转换的元素，避免反复转换，即hit-->hot-->hit-->hot .....

3、效率太低，在第一步的时候大量尝试无法形成转换的错误序列并尝试递归（能否反向endWord到beginWord？效率会否不同，感觉应该差不多）

class Solution {
    int ret = Integer.MAX_VALUE;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(wordList.size()==0 || wordList.indexOf(endWord)==-1){
            return 0;
        }        
        boolean[] isUsed = new boolean[wordList.size()];
        //最短为1
        permutation(beginWord,endWord,wordList,1,isUsed);
        if(ret == Integer.MAX_VALUE){
            return 0;
        }else{
            return ret;
        }
    }
    
    void permutation(String s, String target, List<String> wordList,int step,boolean[] isUsed){
        // System.out.println(s);
        //isUsed标记当前为是否被使用过,避免重复接龙 a-b-a-b...
        if(s.equals(target)){
            ret = step<ret? step:ret;
            return ;
        }
        for(int i=0 ; i<wordList.size() ; i++){
            if(!isUsed[i] && canTurnTo(s,wordList.get(i))){
                //出现Stack Overflow，猜测是由于重复调用
                int index = i;
                isUsed[index] = true;
                permutation(wordList.get(i),target,wordList,step+1,isUsed);
                isUsed[index] = false;
            }
        }
    }
    
    boolean canTurnTo(String s, String p){
        //默认不可匹配
        boolean flag = false;
        for(int i=0 ; i<s.length() ; i++){
            if(s.charAt(i)!=p.charAt(i)){
                if(flag){
                    //已有标记则至少有两个字符不同返回false
                    return false;
                }else{
                    //出现一次不同标记flag= true
                    flag = true;
                }  
            }
        }
        //全等不可转换
        return flag;
    }
}

version2：不递归回溯如何遍历所有可能结果？层次遍历

1、我的想法是递推关系：建立递推关系：从endWord逆推给List中每个元素建立一个可到达最短的步数索引如：endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]，则 step为 [ len,len,2,len,2,1]，从两个step=2的为剩余3个建立索引...

2、实现的过程类似二叉树的层次遍历，索引使用Queue<String> allSteps分层遍历，使用visited数组对以及逆推建立过联系的元素不再重复访问，因为可能会赋值更长的路径以及出现环

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //建立递推关系：从endWord逆推给List中每个元素建立一个可到达最短的步数索引如：endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]，则 step为 [ len,len,2,len,2,1]，从两个step=2的为剩余3个建立索引...
        int index= wordList.indexOf(endWord);
        if(wordList.size()==0 || index==-1){
            return 0;
        }
        //提前判断是否能一步转换，否则会出现 "a"，"c"，["a","b","c"]，检测到b时发现b可以一步转为c导致非最短路劲
        if(canTurnTo(beginWord,endWord)){
            return 2;
        }
        //是否访问过
        boolean[] visited = new boolean[wordList.size()];
        Arrays.fill(visited,false);
        visited[index] = true;
        //当前N步能到达队列
        Queue<String> allSteps = new LinkedList<>();
        allSteps.offer(endWord);
        //当前处理步数索引
        index = 1;
        //Map：key = string ，val = string到达endWord的步数
        Map<String,Integer> m = new HashMap<>();
        m.put(endWord,index);
        
        while(!allSteps.isEmpty()){
            //取当前步数相同层的长度
            int len = allSteps.size();
            while(len-->0){
                String str = allSteps.poll();
                index = m.get(str);
                for(int j=0 ; j<wordList.size() ; j++){
                    if(visited[j]){
                        //不要放在for循环内写，否则遇到第一个访问过的跳出
                        continue;
                    }
                    if(canTurnTo(str,wordList.get(j))){
                        //可一步转化则访问
                        visited[j] = true;
                        //当前String与beginWord是否可以一步转化
                        if(canTurnTo(wordList.get(j),beginWord)){
                            return index+2;
                        }
                        allSteps.add(wordList.get(j));
                        //将当前String记录为下一层步数
                        m.put(wordList.get(j),index+1);
                    }
                } 
            }
        }
        return 0;
    }
    
    //是否可以一步到达
    boolean canTurnTo(String s, String p){
        //记录两个字符串的不符字符个数
        int misMatch = 0;
        for(int i=0 ; i<s.length() ; i++){
            if(s.charAt(i)!=p.charAt(i)){
                misMatch++;
            }
        }
        return misMatch==1;
    } 
}