[LeetCode] 139. Word Break 拆分词句
2024-08-30 19:50:41
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
这道拆分词句问题是看给定的词句能分被拆分成字典里面的内容,这是一道很经典的题目,解法不止一种,考察的范围很广,属于我们必须要熟练掌握的题目。那么先来想 brute force 的解法,就拿例子1来分析,如果字典中只有两个单词,我们怎么去判断,是不是可以将原字符串s分成任意两段,然后再看分成的单词是否在字典中。注意这道题说是单词可以重复使用,所以可以分成任意段,而且字典中的单词可以有很多个,这就增加了题目的难度,很多童鞋就在这里迷失了,毫无头绪。那么,就由博主来给各位指点迷津吧(此处应有掌声
最新文章
- C# rename方法重命名文件
- windows下同时安装python2与python3
- CentOS提示::unknown filesystem type 'ntfs'.解决
- cocos2d jsb 打包 Android APK
- Centos6.4 安装NLTK
- 【总结】教你怎么将centos7打造成桌面系统
- php 写session
- 51nod算法马拉松 contest7
- Spark算子总结及案例
- PHP工厂模式
- js写基础insertAfter()方法
- [LeetCode] 2 Keys Keyboard 两键的键盘
- Java面试题之Forward和Redirect的区别
- encoding and Endian
- 分布式版本控制系统GIT的使用
- SignalR WebSocket Error during WebSocket handshake: net::ERR_CONNECTION_RESET
- HTML+CSS+JS 传智 详细笔记
- MongoDb进阶实践之一 如何在Linux系统上安装和配置MongoDB
- 如何从angular2中的url获取查询参数?
- Java编程的逻辑 (31) - 剖析Arrays