Leetcode每日一题:127.word-ladder(单词接龙)

标签: Leetcode  dfs  算法  动态规划

在这里插入图片描述
思路:树的层次遍历,BFS,注意这里如果用bool数组标记该字符串是否加入过序列,肯定会超时,因为每次都要遍历整个wordList,所以,建议将加入序列的字符串从wordList中删除,勉强过关;DFS+回溯肯定超时,不用想;
在这里插入图片描述
借用评论:
优先广度、深度搜索,最下策再回溯法,因为回溯会有很多问题;
滑动窗口、双指针、dfs/bfs、动态规划、回溯,以后就按照这个顺序思考问题;
动态规划比较难想;

class Solution
{
public:
    bool check(string a, string b)
    {
        bool flag = true;
        int len = a.size();
        for (int i = 0; i < len; i++)
        {
            if (!flag && a[i] != b[i])
            {
                return false;
            }
            if (a[i] != b[i])
            {
                flag = false;
            }
        }
        return true;
    }

    int ladderLength(string beginWord, string endWord, vector<string> &wordList)
    {
        int len2 = wordList.size();
        if (len2 == 0)
        {
            return 0;
        }
        int count = 1;

        queue<string> q;
        q.push(beginWord);
        while (!q.empty())
        {
            int q_len = q.size();
            count++;
            while (q_len--)
            {
                string now = q.front();
                q.pop();
                for (int i = 0; i < wordList.size(); i++)
                {
                    if (check(now, wordList[i]))
                    {
                        if (wordList[i] == endWord)
                        {
                            return count;
                        }
                        q.push(wordList[i]);
                        wordList.erase(wordList.begin() + i);
                        i--;
                    }
                }
            }
        }
        return 0;
    }
};
版权声明:本文为wyll19980812原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wyll19980812/article/details/109503689

智能推荐

springMVC拦截器

一、     SpringMVC拦截器实现原理 用户请求到DispatherServlet中,DispatherServlet调用HandlerMapping查找Handler,HandlerMapping返回一个拦截器链(HandlerExecutionChain),springmvc中的拦截器是通过HandlerMapping发起的。 &nbs...

Unity Json反序列化

Json反序列化 结果:...

[机器学习-回归算法]Sklearn之线性回归实战

Sklearn之线性回归实战 一,前言 二,热身例子 三,贸易公司的简单例子 四,Sklearn 官网里的一个例子 参考资料 一,前言 一元线性回归的理论片请看我这个链接 二,热身例子 预测直线 y=1x1+2x2+3y = 1x_1 + 2x_2 +3y=1x1​+2x2​+3 导入LinearRegression 从Sklearn.liear_model 包里 拟合数据也可以说是训练 检验正确...

Android 开发者,你真的懂 Context 吗?

Android Context 详解 前言 一、Context是什么 二、Context结构 1、ContextImpl类介绍 2、ContextWrapper类介绍 3、ContextThemeWrapper 三、Context的数量 四、Context注意事项 五、如何正确回复以上面试题? 前言 Context 相信所有的 Android 开发人员基本上每天都在接触,因为它太常见了。但是这并不...

SpringMVC ----Json的简单交互处理

SpringMVC--Json Json的介绍 什么是JSON? JSON 和 JavaScript 对象互转 Controller返回JSON数据 Jackson 乱码 乱码的解决方法一 代码优化 乱码统一解决方法 返回json字符串统一解决 测试多个对象的集合输出 输出时间对象 抽取为工具类 FastJson fastjson 三个主要的类: JSONObject JSONArray JSON...

猜你喜欢

微信小程序自定义组件简单实现

本文将教你如何实现一个自定义的toast提示框,实现后的基本效果图如下: 小程序中一个自定义组件由 json wxml wxss js 4个文件组成的。下面我们一步一步地来创建文件及完成其中的配置: step1:创建自定义组件 首先创建一个components文件夹,用于放置所有自定义的组件,创建之后的目录结构为 其中的toastedit是我们本次...

PyTorch学习(四)--用PyTorch实现线性回归

教程视频:https://www.bilibili.com/video/BV1tE411s7QT 废话不多说,代码如下: 结果: 0 56.52023696899414 1 25.170454025268555 2 11.214292526245117 3 5.001270771026611 4 2.2352840900421143 5 1.0038176774978638 6 0.4554775...

1、Qt 的窗口组件和窗口类型

1、窗口组件 图形用户界面由不同的窗口和窗口组件组成 组件的类型 — 容器类(父组件):用于包含其它的界面组件 — 功能类(子组件):用于实现特定的交互功能 Qt 中没有父组件的顶级组件叫做窗口 QWidget QWidget 继承于 QObject 和 QPaintDevice — QObject 是所有支持 Qt 对象模型的基类 — QPaint...

从APP跳转到微信指定联系人聊天页面功能的实现与采坑之旅

从APP跳转到微信指定联系人聊天页面功能的实现与采坑之旅 起因 实现逻辑 效果图 实现过程 跳转微信按钮点击事件 无障碍监听主要方法 一些必要的参数 监听主要方法 遇到的坑 1. 搜索内容无法赋值给搜索框 2. 如何停止监听? 3. 没查询到结果如何停止监听? 4. 如果在微信其他页面怎么办? 5. 页面改变UI加载太慢 6. 聊天界面和主页面是同一个活动 7. 搜索不到结果时,发现他在搜索结果页...

6.ROI与泛洪填充

学习视频可参见python+opencv3.3视频教学 基础入门 ROI与泛洪填充 1.ROI ROI(region of interest),感兴趣区域 对lena图进行脸部的获取,代码如下 注意转化转化后的灰度图是单通道的,所以要转成三通道进行合并 结果如下 2.泛洪填充 简而言之,就是把你想要填充的区域填充成你想要的颜色 Iimage:输入图像,可以是一通道或者是三通道。 seedPoint...