[leetcode] 139. Word Break

[leetcode] 139. Word Break

Description

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

分析

题目的意思是：判断一个字符串能否分割成若干个字典中的单词。

dp[i] 表示源串的前i个字符可以满足分割，那么 dp[ j ] 满足分割的条件是存在k 使得 dp [k] && substr[k,j]在字典里。

代码

class Solution {public: bool wordBreak(string s, vector& wordDict) { vector dp(s.size()+1,false); dp[0]=true; for(int i=0;i

参考文献

​​[编程题]word-break​​​​[Leetcode] Word Break、Word BreakII​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。