【LeetCode每天一题】Word Break()

【LeetCode每天一题】Word Break()

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

思路

  在做这道题的时候比较有意思的是我想了两种方法来解决,但是两种方法都没有能ac,第一种方法大概就是我从字符串s的第一个开始遍历并申请一个tem变量来记录为被匹配的字符串,当匹配到字符串之后重新将tem设置为"",最后遍历完毕之后判断tem是否为空从而得到是否可以满足。这种思路缺陷就是我们能考虑有一种情况就是s="aaaaaaa", wordlidt=["aaaa", "aaa"],对于这个情况,她会每次都先匹配"aaa",这样导致最后还剩下一个"a"。输出False,所以不正确。
  在上一种方法的特殊情况下,我想到了使用递归,大概就是从头开始遍历遍历,当遇到列表中存在的单词时,我们将s以匹配的单词去除作为参数进行递归,重新开始进行匹配。最后如果能匹配就可以得到True。但是这种解法最后因为超时也没能AC。
  看了别人的答案之后发现原来还能使用动态规划来解决,大概思路就是申请一个比s字符串长1的辅助数组,初始化为False,第一个元素初始化True。最后我们设置两层循环,第一层循环就是判断辅助数组每一位是否能有列表中的单词组合成,内层循环表示从0开始到第一层循环当前遍历的位置,对每一种可能的字符串判断是否在列表中。当最后遍历完毕之后,辅助数组最后一个元素就是结果。
图解思路

解决代码


 1 class Solution(object):  2     def wordBreak(self, s, wordDict):  3         """
 4  :type s: str  5  :type wordDict: List[str]  6  :rtype: bool  7         """
 8    
 9         if not s: 10             return True 11         dp = [False] *(len(s)+1) # 申请辅助数组 12         dp[0] = True # 第一个设置为True 13         for i in range(1, len(s)+1): # 外层循环 14             for j in range(i): # 内存循环 15                 if dp[j] and s[j:i] in wordDict: # 判断条件 16                     dp[i] = True 17                     break
18         return dp[-1]

附上递归解法(s字符串过长时会超时)
 1 class Solution(object):  2     def wordBreak(self, s, wordDict):  3         """
 4  :type s: str  5  :type wordDict: List[str]  6  :rtype: bool  7         """
 8         
 9         if not s: 10             return True 11         res= [] 12  self.Bfs(s, wordDict, res) # 进行递归遍历 13         if not res: 14             return False 15         return True 16         
17         
18     def Bfs(self, s, wordDict, res): 19         if not s: # 如果s为空表示能够匹配, 20  res.append(True) 21             return 
22         tem = ""
23         for i in range(len(s)): # 从头开始遍历 24             tem += s[i] # 记录未匹配的值 25             if tem in wordDict: # 当匹配到后,我们进行将s进行切割, 26                 self.Bfs(s[i+1:], wordDict, res)    

转载于:https://www.cnblogs.com/GoodRnne/p/10950784.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100888.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • stemwin实战篇_赖世雄入门篇

    stemwin实战篇_赖世雄入门篇特别说明:原创教程,未经许可禁止转载,教程采用回复可见的形式,谢谢大家的支持。armfly-x2,x3,v2,v3,v5开发板裸机和带系统的emWin工程已经全部建立,链接如下:http://bbs.

  • pip卸载包命令_pip怎么卸载

    pip卸载包命令_pip怎么卸载在用pip卸载Django相关的模块时,由于操作不当,造成异常,结果再次执行piplist时,发现如下结果通过pip尝试了半天,对于这些异常的列表信息无法处理。最后,在相应的包安装目录下(本例为C:\ProgramFiles\Python37\Lib\site-packages)查看到如下情况将所有有前缀的文件夹(除了__pycache__文件夹)删除,重新执行pip…

    2022年10月17日
  • UFT12的破解方法和UFT11.5一致

    UFT12的破解方法和UFT11.5一致UFT12的破解方法和UFT11.5一致,不能永久破解,只能试用30天后重新破解。 方法:1.删除C:\ProgramData隐藏目录下的SafeNetSentinel文件夹2.运行QTP安装目录下的bin\instdemo.exe3.重新运行QTP/UFT12后即可恢复30天试用

  • android之Unable to execute dex: Multiple dex files define「建议收藏」

    出现了异常Dex Loader:Unable to execute dex: Multiple dex files define Landroid/support/v4/accessibilityservice/AccessibilityServiceInfoCompat$AccessibilityServiceInfoVersionImpl; 查了好多方法都不行,最后得到了解决方法:

  • sqlite 锁机制_SQLite读写为什么冲突

    sqlite 锁机制_SQLite读写为什么冲突sqlite读写锁SQLite3总共有三种事务类型:BEGIN[DEFERRED/IMMEDIATE/EXCLUSIVE]TRANSCATION,提供以下五种的文件锁状态,按锁的级别依次是:UNLOCKED/SHARED/RESERVERD/PENDING/EXCLUSIVE。1).UNLOCKED:无锁  文件没有持有任何锁,即当前数据库不存在任何读或写…

  • 币圈新手入门教程 怎么样投资数字货币[通俗易懂]

    币圈新手入门教程 怎么样投资数字货币[通俗易懂]普通人怎么投资数字货币?最近和几位朋友聊到数字货币,发现很多人虽然都想入场交易,但实际上还不是很了解这个东西,这对于新手来说,是非常危险的!笔者尽管现在主要做的是外汇,但是曾经也炒币有一段时间,今天就以自己的经验,给各位币圈新手做个入门普及。数字货币说到数字货币,先要了解区块链,数字货币实际上是区块链的一个产物,数字货币都是由区块链技术产生的,而区块链技术近几年的快速发展,也推动了数字货币…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号