首页 > 其他分享 >139.单词拆分

139.单词拆分

时间:2023-03-12 13:12:09浏览次数:42  
标签:return dfs 单词 start 拆分 wordDict 139 true size

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

示例 1:

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
  注意,你可以重复使用字典中的单词。
示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路1:dfs worddict中的所有组合

见注释。

code

class Solution {
public:
    //DFS 遍历所有的可能性
    //a tree of dfs

    bool dfs(string & s,vector<string> & wordDict,int start)
    {
        if(start >= s.size()) return true;

        for(int i = 0;i < wordDict.size();i ++)
        {
            int j;
            for(j = 0;j < wordDict[i].size();j ++)
            {
                if(s[start + j] == wordDict[i][j]) continue;
                else break;
            }
            if(j == wordDict[i].size())
            {
                if(dfs(s,wordDict,start + j)) return true;
            }

        }

        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        
        return dfs(s,wordDict,0);
    }
};

解题思路2 : 记忆化搜索优化

见注释

code

class Solution {
public:
    //DFS 遍历worddict所有组合的可能性
    //a tree of dfs
    //渐渐擅长写dfs
    //可惜超时了
    
    //由于回溯机制的存在,同一个start可能会被重复搜索,但是由于worddict相同,无论重复多少次结果都是相同的
    //只需要将之前遍历的一个start的结果存储下来,后面就可以避免重复的搜索

    bool dfs(string & s,vector<string> & wordDict,vector<int> & mem,int start)
    {
        if(start >= s.size()) return true;

        if(mem[start] != -1) return mem[start];

        for(int i = 0;i < wordDict.size();i ++)
        {
            int j;
            for(j = 0;j < wordDict[i].size();j ++)
            {
                if(s[start + j] == wordDict[i][j]) continue;
                else break;
            }
            if(j == wordDict[i].size())
            {
                if(dfs(s,wordDict,mem,start + j)) return true;
            }

        }

        mem[start] = false;
        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        vector<int> mem(s.size(),-1);
        return dfs(s,wordDict,mem,0);
    }
};

解题思路3:dfs 字符串的前缀

见注释

code

class Solution {
public:
    //换一种dfs的写法
    //遍历s的前缀判断是否在worddict中

    bool dfs(string & s,vector<string> & wordDict,int start)
    {
        if(start >= s.size()) return true;

        for(int i = start;i < s.size();i ++)
        {
            string prefix = s.substr(start,i - start + 1);
            if(find(wordDict.begin(),wordDict.end(),prefix) != wordDict.end() && dfs(s,wordDict,i + 1))
            {
                return true;
            }
        }
        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        
        return dfs(s,wordDict,0);
    }
};

解题思路4:记忆化搜索优化

见注释。

code

class Solution {
public:
    //换一种dfs的写法
    //遍历s的前缀判断是否在worddict中
    
    //时间复杂度:2 ^ n
    //时间复杂度高的原因是重复的结果被大量计算
    //比如aaaaaaab,wordict中存在一个a
    //那么start就会不断递增下去,直到碰到b
    //如果worddict有aa,start也会不断递增下去,由于使用的worddict是相同的,没有必要继续下去了,之前的start的不行,现在还是相同的start位置,相同的worddict也是不行
    //存储每一个start位置的结果即可

    bool dfs(string & s,vector<string> & wordDict,vector<int> & mem,int start)
    {
        if(start >= s.size()) return true;

        if(mem[start] != -1) return mem[start];

        for(int i = start;i < s.size();i ++)
        {
            string prefix = s.substr(start,i - start + 1);
            if(find(wordDict.begin(),wordDict.end(),prefix) != wordDict.end() && dfs(s,wordDict,mem,i + 1))
            {
                return true;
            }
        }
        mem[start] = false;
        return false;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<int> mem(n,-1);//-1 uninitialized 0 false  1 ture    
        return dfs(s,wordDict,mem,0);
    }
};

解题思路5:动态规划

见注释

code

class Solution {
public:
    //动态规划
    //状态表示:f[i]前i个字符是否可以划分为worddict中的单词
    //状态转移:f[j]且[j+1]->[i]是worddict中的单词
    //为了避免处理麻烦的边界条件,f[0] = true表示空字符串

    bool wordBreak(string s, vector<string>& wordDict) {
        
        int n = s.size();
        vector<bool> f(n + 1,false);
        
        f[0] = true;

        for(int i = 1;i <= n;i ++)
        {
            f[i] = false;
            for(int j = i;j > 0;j--)
            {
                if(f[j-1] && find(wordDict.begin(),wordDict.end(),s.substr(j-1,i - j + 1)) != wordDict.end() ) f[i] = true;
            }
        }

        return f[n];
    }
};

标签:return,dfs,单词,start,拆分,wordDict,139,true,size
From: https://www.cnblogs.com/huangxk23/p/17208010.html

相关文章

  • leetcode-1394-easy
    FindLuckyIntegerinAnArrayGivenanarrayofintegersarr,aluckyintegerisanintegerthathasafrequencyinthearrayequaltoitsvalue.Returnthe......
  • 华为OD机试 单词接龙
    ......
  • 拆分逗号为数组,判断是否匹配
    拆分逗号为数组,判断是否匹配string[]array1="jankiE,aaA".Split(',');List<string>listLower=newList<string>();foreach(stringsinarray1){listLowe......
  • 云图说丨云数据库GaussDB(for MySQL)事务拆分大揭秘
    摘要:数据库代理提供事务拆分的功能,能够将事务内写操作之前的读请求转发到只读节点,降低主节点负载。本文分享自华为云社区《【云图说】第270期云数据库GaussDB(forMySQL)......
  • 79.单词搜索
    单词搜索给定一个 mxn二维字符网格 board和一个字符串单词 word。如果 word存在于网格中,返回true;否则,返回false。单词必须按照字母顺序,通过相邻的单元格内......
  • 图形学——单词
    determine确定formulate制定layoutanddimension布局和尺寸spatial空间的3Disovist三维可视域SpaceSampling(DataCollectionUsing3DIsovist)使用3Dinsovist......
  • 如何在服务器端通过命令操作、拆分和合并 PDF 文件
    PDF最初由AdobeSystems于1993年开发,旨在创建一种可以在不同计算机系统、软件应用程序和设备之间轻松共享和打印的文件格式。当时,文档通常以专有文件格式创建,这些文件......
  • 计算最长英语单词链
    课堂练习题目:计算最长英语单词链。一、题目内容:大家经常玩成语接龙游戏,我们试一试英语的接龙吧:一个文本文件中有N个不同的英语单词,我们能否写一个程序,快速找出最长的......
  • 【喜报】高科技PCB行业排头兵企业S/4HANA 1709拆分项目成功上线
    2023年2月20日,SNP与金牌合作伙伴–上海翰耐信息科技有限公司一起合作的高科技行业某客户S/4HANA1709拆分项目成功上线。此项目为SNP中国的又一单S/4拆分项目。祝贺中国......
  • 汉字与字母的彻底拆分(Power Query)
    问题:对混在一起的汉字与字母混进行完全拆分let源=Excel.CurrentWorkbook(){[Name="表1"]}[Content],从中文到字母拆分列=Table.SplitColumn(源,"列1",Sp......