leetcode单词接龙-阿里云开发者社区

公众号merlinsea

链接：

https://leetcode.cn/problems/word-ladder/

题目描述：

字典 wordList 中从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

题目分析：

通过上述题目描述可以知道beginWord可以不在wordList字典序列中，endWord必须存在字典序列中。
上述问题可以抽象成一个图，所有的单词都是图中的节点，边代表这两个节点之间是否可以相互转换。
通过广度优先遍历的方法一圈一圈向外扩展，当第一次遇见endWord的时候就返回遍历的圈数即为答案。

c++代码实现[基于邻接矩阵实现]：

//基于邻接矩阵
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int beginIdx = -1;
        int endIdx= -1;
        //找单词 是否存在endWord和beginWord
        for(int i=0;i<wordList.size();i++){
            if(wordList[i]==beginWord){
                beginIdx = i;
            }
            if(wordList[i]==endWord){
                endIdx = i;
            }
        }
        if(endIdx == -1){
            //不存在这endWord
            return 0;
        }
        if(beginIdx == -1){
            wordList.push_back(beginWord);
            beginIdx = wordList.size()-1;
        }
        // 需要从beginIdx --> endIdx
        //建立图
        int n = wordList.size(); //节点的个数
        vector<vector<int>> graph(n,vector<int>(n,0));
        createGraph(graph,wordList);
        //广度优先搜索
        int layer = bfs(graph,beginIdx,endIdx);
        return layer;
    }
    int bfs(vector<vector<int>>& graph,int beginIdx,int endIdx){
        int n = graph.size();
        vector<bool> isVisited(n,false);
        queue<int> qu;
        int cnt = 1;  // 代表当前层的节点个数
        int layer = 0;
        qu.push(beginIdx);
        int cur = -1;
        while(!qu.empty()){
            // 说明第1圈刚开始
            int nextCnt = 0; // 代表下一圈的节点
            layer++;
            int i;
            for(i=0;i<cnt;i++){
                cur = qu.front();
                qu.pop();
                isVisited[cur] = true;
                if(cur == endIdx){
                    break;
                }
                //遍历cur的邻居节点并且如果没有访问过就加入队列
                for(int j=0;j<n;j++){
                    if(graph[cur][j]==1 && !isVisited[j]){
                        qu.push(j);
                        nextCnt++;
                    }
                }
            }
            if(i<cnt){
                break;
            }
            cnt = nextCnt;
        }
        // 退出循环，我们并不能确定是break退出的，
        // 如果是break退出的，那么肯定找到了
        // 如果是while循环正常退出，说明是存在endIdx，但是beginIdx和endIdx之间没有边---》 非连通图
        if(cur != endIdx){
            layer = 0;
        }
        return layer;
    }
    void createGraph(vector<vector<int>>& graph,vector<string>& wordList){
        for(int i=0;i<wordList.size();i++){
            for(int j=0;j<wordList.size();j++){
                //判断 wordList[i] 和 wordList[j]是否可以相互转换
                int diff = judgeEdge(wordList[i],wordList[j]);
                if(diff == 1){
                    //才可以相互转换
                    graph[i][j] = 1;
                    graph[j][i] = 1;
                }
            }
        }
        //建立好了图
    }
    int judgeEdge(string str1,string str2){
        if(str1.size() != str2.size()){
            return 0;
        }
        int diff = 0;
        for(int i=0;i<str1.size();i++){
            if(str1[i]!=str2[i]){
                diff++;
            }
            if(diff == 2){
                break;
            }
        }
        return diff;
    }
};

c++代码实现[基于邻接表实现]：

// 邻接表的解法
//定义节点
struct Node{
    int val; // 下标 wordList里面的下标
    Node* next;
    Node(int x):val(x),next(nullptr){}
};
class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        int beginIdx = -1;
        int endIdx = -1;
        for(int i=0;i<wordList.size();i++){
            if(wordList[i]==beginWord){
                beginIdx = i;
            }
            if(wordList[i]==endWord){
                endIdx = i;
            }
        }
        if(endIdx==-1){
            return 0;
        }
        if(beginIdx==-1){
            wordList.push_back(beginWord);
            beginIdx = wordList.size()-1;
        }
        // 建立图
        //vector<Node*> graph(wordList.size(),new Node(0)); 不行
        vector<Node*> graph(wordList.size());
        for(int i=0;i<graph.size();i++){
            graph[i] = new Node(0);
        }
        createGraph(graph,wordList);
        //用bfs 求路径长度
        int len = bfs(graph,beginIdx,endIdx);
        return len;
    }
    int bfs(vector<Node*>& graph,int beginIdx,int endIdx){
        vector<bool> isVisited(graph.size(),false);
        queue<int> qu;
        //队列初始
        qu.push(beginIdx);
        int cnt = 1; //当前层的个数
        int layer = 0; //走了多少圈
        int cur = -1;
        while(!qu.empty()){
            //说明当前层刚开始
            int nextCnt = 0;//下一层的个数
            layer++;
            for(int i=0;i<cnt;i++){
                cur =qu.front();
                qu.pop();
                isVisited[cur] = true;
                if(cur == endIdx){
                    break;
                }
                //遍历邻居节点
                Node* neighborHead = graph[cur]; // 虚拟的
                Node* neighbor = neighborHead->next;
                while(neighbor!=nullptr){
                    int idx =neighbor->val;
                    if(!isVisited[idx]){
                        //入队
                        qu.push(idx);
                        nextCnt++;
                    }
                    neighbor = neighbor->next;
                }
            }
            if(cur == endIdx){
                break;
            }
            cnt = nextCnt;
        }
        //layer!=0  
        //如果图是不连通的，那么其实也是没有找到元素
        if(cur != endIdx){
            layer = 0;
        }
        return layer;
    }
    void createGraph(vector<Node*>& graph,vector<string>& wordList){
        for(int i=0;i<wordList.size();i++){
            for(int j=i+1;j<wordList.size();j++){
                //判断单词是否可以转换
                int diff = judgeEdge(wordList[i],wordList[j]);
                if(diff==1){
                    //可以转换
                    Node* iNode = new Node(i);
                    Node* jNode = new Node(j);
                    // 让iNode插入到graph[j]后面
                    iNode->next = graph[j]->next;
                    graph[j]->next = iNode;
                    //让jNode插入到graph[i]后面
                    jNode->next = graph[i]->next;
                    graph[i]->next = jNode;
                }
            }
        }
        return;
    }
    int judgeEdge(string str1,string str2){
        if(str1.size()!=str2.size()){
            return 0;
        }
        int diff = 0;
        for(int i=0;i<str1.size();i++){
            if(str1[i]!=str2[i]){
                diff++;
            }
            if(diff==2){
                break;
            }
        }
        return diff;
    }
};

java代码实现[基于邻接表]：

class Node{
    int idx;
    Node next;
    Node(int idx){
        this.idx = idx;
        next = null;
    }
}
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int beginIdx = -1;
        int endIdx = -1;
        for(int i=0;i<wordList.size();i++){
            if(beginWord.equals(wordList.get(i))){
                beginIdx = i;
            }
            if(endWord.equals(wordList.get(i))){
                endIdx = i;
            }
        }
        if(endIdx == -1){
            //说明没有找到
            return 0;
        }
        if(beginIdx == -1){
            wordList.add(beginWord);
            beginIdx = wordList.size()-1;
        }
        // 构造邻接表
        List<Node> graph = createGraph(wordList);
        int len = bfs(graph,beginIdx,endIdx);
        return len;
    }
    private int bfs(List<Node> graph,int beginIdx,int endIdx){
        Queue<Integer> qu = new LinkedList<>();
        boolean[] isVisited = new boolean[graph.size()];
        int layer = 0;
        qu.offer(beginIdx);
        int cnt = 1;
        while(!qu.isEmpty()){
            int nextCnt = 0;
            layer++;
            for(int i=0;i<cnt;i++){
                int cur = qu.poll();
                isVisited[cur] = true;
                if(cur == endIdx){
                    return layer;
                }
                Node neighbor = graph.get(cur);
                Node p = neighbor.next;
                while(p!=null){
                    if(!isVisited[p.idx]){
                        qu.offer(p.idx);
                        nextCnt++;
                    }
                    p = p.next;
                }
            }
            cnt = nextCnt;
        }
        // return 0是因为可能是一个非联通图
        return 0;
    }
    private List<Node> createGraph(List<String> wordList){
        List<Node> graph = new ArrayList<>();
        for(int i=0;i<wordList.size();i++){
            graph.add(new Node(i));
        }
        for(int i=0;i<wordList.size();i++){
            for(int j=i+1;j<wordList.size();j++){
                boolean r = judgeEdge(wordList.get(i),wordList.get(j));
                if(r){
                    Node iNode = new Node(i);
                    Node jNode = new Node(j);
                    iNode.next = graph.get(j).next;
                    graph.get(j).next = iNode;
                    jNode.next = graph.get(i).next;
                    graph.get(i).next = jNode;
                }
            }
        }
        return graph;
    }
    private boolean judgeEdge(String word1,String word2){
        if(word1.length() != word2.length()){
            return false;
        }
        int diff = 0;
        for(int i=0;i<word1.length();i++){
            if(word1.charAt(i)!=word2.charAt(i)){
                diff++;
            }
        }
        return diff == 1;
    }
}

java代码实现[基于邻接矩阵]：

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int beginIdx = -1;
        int endIdx = -1;
        for(int i=0;i<wordList.size();i++){
            if(beginWord.equals(wordList.get(i))){
                beginIdx = i;
            }
            if(endWord.equals(wordList.get(i))){
                endIdx = i;
            }
        }
        if(endIdx == -1){
            //说明没有找到
            return 0;
        }
        if(beginIdx == -1){
            wordList.add(beginWord);
            beginIdx = wordList.size()-1;
        }
        // 构造邻接表
        int[][] graph = createGraph(wordList);
        int len = bfs(graph,beginIdx,endIdx);
        return len;
    }
    private int bfs(int[][] graph,int beginIdx,int endIdx){
        Queue<Integer> qu = new LinkedList<>();
        boolean[] isVisited = new boolean[graph.length];
        int layer = 0;
        qu.offer(beginIdx);
        int cnt = 1;
        while(!qu.isEmpty()){
            int nextCnt = 0;
            layer++;
            for(int i=0;i<cnt;i++){
                int cur = qu.poll();
                isVisited[cur] = true;
                if(cur == endIdx){
                    return layer;
                }
                for(int j=0;j<graph.length;j++){
                    if(graph[cur][j]==1 && !isVisited[j]){
                        qu.offer(j);
                        nextCnt++;
                    }
                }
            }
            cnt = nextCnt;
        }
        // return 0是因为可能是一个非联通图
        return 0;
    }
    private int[][] createGraph(List<String> wordList){
        int[][] graph = new int[wordList.size()][wordList.size()];
        for(int i=0;i<wordList.size();i++){
            for(int j=0;j<wordList.size();j++){
                boolean r = judgeEdge(wordList.get(i),wordList.get(j));
                if(r){
                    graph[i][j] = graph[j][i]=1;
                }
            }
        }
        return graph;
    }
    private boolean judgeEdge(String word1,String word2){
        if(word1.length() != word2.length()){
            return false;
        }
        int diff = 0;
        for(int i=0;i<word1.length();i++){
            if(word1.charAt(i)!=word2.charAt(i)){
                diff++;
            }
        }
        return diff == 1;
    }
}

vip永久班算法直播教学，手把手带你刷leetcode，详情如下：

奔跑的小梁，公众号：梁霖编程工具库leetcode刷题永久班直播教学，手把手带你刷题，价格调整通知，2022年11月14日

leetcode单词接龙

热门文章

最新文章

相关电子书