LeetCode139. Word Break DP算法

本文主要是介绍LeetCode139. Word Break DP算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

139. Word Break

动态规划DP算法

题意：

Medium

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"

解题过程：

 

代码：

Java

class Solution {public boolean wordBreak(String s, List<String> wordDict) {boolean[] dp=new boolean[s.length()+1];dp[0]=true;for(int i=1;i<s.length()+1;++i){for(int j=0;j<i;++j){if(dp[j]&&wordDict.contains(s.substring(j,i))){dp[i]=true;break;}}}return dp[s.length()];}
}

Python

class Solution:def wordBreak(self, s: str, wordDict: List[str]) -> bool:dp=[False]*(len(s)+1)dp[0]=Truefor i in range(1,len(s)+1):for j in range(0,i):if dp[j] and s[j:i] in wordDict:dp[i]=Truereturn dp[-1]

 

这篇关于LeetCode139. Word Break DP算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---