• leetcode经典例题——单词拆分


    单词拆分

    题目描述:

       1、动态规划

    思路:这道题是要我们单词拆分来,能用字符串列表这个数组组成,我们就可以用到动态规划:

    初始化 dp=[false,……,false],长度为 n+1。n 为字符串长度。dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示。初始化 dp[0]=True,空字符可以被表示。

    当我们遍历s单词字符串时,如果dp[i] =false,则退出循环,证明我们无法拼接到这个位置;

    如果dp[i] = true,我们遍历字符串列表,依次匹配,看是否能匹配至s单词字符串,匹配成功,则设置该位置dp[word.length+1] = true;

    看看代码:

    1. public boolean wordBreak(String s, List wordDict) {
    2. int len = s.length();
    3. boolean[] dp = new boolean[len+1];
    4. dp[0] = true;
    5. for(int i = 0;i
    6. if(!dp[i]) continue;
    7. for(String word : wordDict){
    8. if (s.startsWith(word,i))
    9. dp[word.length()+i] = true;
    10. }
    11. }
    12. return dp[len];

     时间复杂度:O(m*n),m为单词s的长度,n为字典wordDict的数量

    空间复杂度:O(n)

    2、回溯算法

    思路:这道题既然是依次拼接,也就是一道排列组合题,我们也可以用回溯算法来解决

    回溯算法就也是利用遍历wordDict,判断s.startsWith(word,i)为true时进行递归,

    如果该次递归成功,我们返回结果true;

    如果该次递归不成功,我们回溯,仍旧遍历wordDict进行判断是否下一次递归,直到wordDict遍历完成,仍没结果才返回false;

    进入代码:

    1. public boolean wordBreak(String s, List wordDict) {
    2. return backTrack(0,s,wordDict);
    3. }
    4. public boolean backTrack(int len,String s,List wordDict){
    5. if (len == s.length()) return true;
    6. for (String word : wordDict) {
    7. if (s.startsWith(word,len)){
    8. if (backTrack(len+word.length(),s,wordDict))
    9. return true;
    10. }
    11. }
    12. return false;
    13. }

    注:该回溯算法有一个弊端,在leetcode运行时,由于它设置一个单词s为aaaaaaaaaaaaaa……wordDict["a","aa","aaa",……],我们用回溯算法时,由于会优先进行第一个"a"的匹配,所以可能出现超时情况!

    持续更新关于leetcode的文章中~

  • 相关阅读:
    浅浅的整理一下机器学习简单资料
    基于随机森林算法完成鸢尾花卉品种预测任务 代码+数据
    高速电路逻辑电平转换设计
    野火A7学习第十次(状态机相关)
    php-java-net-python-报修修改计算机毕业设计程序
    设计模式之适配器模式(五)
    深入理解Nginx~Nginx配置的通用语法
    IIC总线
    推荐学java——MyBatis高级
    工业网关连接工业生产设备与物联网系统的关键设备
  • 原文地址:https://blog.csdn.net/weixin_72076848/article/details/126166124