首页 > 其他分享 >LeetCode 127 Word Ladder

LeetCode 127 Word Ladder

时间:2022-08-17 04:11:10浏览次数:50  
标签:wordList Word words sequence int Ladder beginWord endWord LeetCode

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord
    Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Solution

注意到每次只能变一个字符,所以我们可以遍历每一个位置,将其设置为 \(\#\),然后用 \(map\) 映射到 \(string\) 的 \(vector\) 里面。所以我们就可以利用 \(BFS\) 的方式,其中队列里面存储 \(pair(str, step)\)

点击查看代码
class Solution {
private:
    unordered_map<string, vector<string>> mp;
    queue<pair<string, int>> q;
    unordered_map<string,int> vis;
    
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(count(wordList.begin(), wordList.end(), endWord)==0)
            return 0;
        int n = wordList.size();
        wordList.push_back(beginWord);
        int m = wordList[0].size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                string tmp = wordList[i].substr(0,j)+'#'+wordList[i].substr(j+1,m-j-1);
                mp[tmp].push_back(wordList[i]);
            }
        }
        q.push({beginWord, 1});
        while(!q.empty()){
            auto f = q.front();q.pop();
            vis[f.first]=1;
            string cur = f.first;
            int cur_step = f.second;
            for(int i=0;i<m;i++){
                string tmp = cur.substr(0,i)+'#'+cur.substr(i+1,m-i-1);
                for(auto t:mp[tmp]){
                    if(!vis[t]){
                        if(t==endWord)return cur_step+1;
                        q.push({t, cur_step+1});
                    }
                }
            }
            
        }
        return 0;
    }
};

标签:wordList,Word,words,sequence,int,Ladder,beginWord,endWord,LeetCode
From: https://www.cnblogs.com/xinyu04/p/16593559.html

相关文章

  • leetcode 热题100刷题-两数之和
    题题号:1题目:两数之和难度:简单链接:https://leetcode.cn/problems/two-sum/2022/08/16答案算法思路从第i个数字开始,之后的每个数字都与第i个数字相加,判断是否与目标值......
  • LeetCode 螺旋矩阵 II 算法题解 All In One
    LeetCode螺旋矩阵II算法题解AllInOnejs/ts生成螺旋矩阵螺旋矩阵原理图解动态赋值arr[i]//动态更新indexleti=0;while(left<=right&&t......
  • leetcode85-最大矩形
    最大矩形dp+单调栈对每一层维护本列中形成的最高值height,然后对每一层分别计算最大的矩形。计算每一层最大矩形的时候,先用单调栈记录小于当前位置的左下标和右下标,矩......
  • leetcode1175-质数排列
    质数排列分别找出质数和合数的数量,将两者的阶乘相乘即可classSolution{publicintnumPrimeArrangements(intn){intcnt=0;for(inti=2;......
  • leetcode690-员工的重要性
    员工的重要性dfsclassSolution{Map<Integer,Employee>map=newHashMap<>();publicintgetImportance(List<Employee>employees,intid){......
  • leetcode1033-移动石子直到连续
    移动石子直到连续分类讨论classSolution{publicint[]numMovesStones(inta,intb,intc){if(a>b){intt=a;a=b;b=t;}if(a>......
  • 使用Xshell连接阿里云无法输入password
    首先打开云服务器点击远程连接用vcn的连接方式去修改sshd的配置文件命令为:vi/etc/ssh/sshd_config按照官方给的错误提示进入编辑后发现参数没有问题于是乎我重......
  • POI生成word设置的字体不生效
    原始修改字体XWPFRunrun=para.createRun();run.setText(runText,0);run.setFontFamily("仿宋");//字体run.setFontSize(16);//字体大小修改中文字体XWPFRunrun......
  • jdbc-windows环境下mysql出现Access denied for user ‘root’@‘localhost’ (using
    1.遇到这个问题后,排查用户名密码、远程连接是否开启、服务是否正常启动、重启mysql服务、用navicat测试能否正常连接2.上述操作均不能发现问题3.在windows内用超级管理员......
  • leetcode-双指针-21
    /**<p>给你一个数组<code>nums</code><em></em>和一个值<code>val</code>,你需要<strong><ahref="https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3......