LeetCode 139. Word Break

139. Word Break

Total Accepted: 131482
Total Submissions: 457810
Difficulty: Medium
Contributors: Admin

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. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

Subscribe to see which companies asked this question.

【题目分析】

给定一个目标字符串和一个字符串列表，判断目标字符串是否能由字符串列表中的串组合而成。

【思路】

1. DP套路多，把大问题分解为子问题还是很考验难度的。

2. 要认真分析，不要急躁。

3. 要注意下标

4. 在本问题中，判断一个大的字符串是否可以被组合成功，可以分解为s.substring(0,i)和substring(i, s.length()),(0=<i<s.length())是否存在一个i使得被分成两部分的字符串都可以被列表中的串组合成功。

【java代码】

 1 public class Solution {
 2     public boolean wordBreak(String s, List<String> wordDict) {
 3         boolean[] flag = new boolean[s.length()+1];
 4         flag[0] = true;
 5         
 6         for(int i = 1; i <= s.length(); i++) {
 7             for(int j = i-1; j >= 0; j--) {
 8                 if(flag[j] && wordDict.contains(s.substring(j,i))) {
 9                     flag[i] = true;
10                     break;
11                 }
12             }
13         }
14         
15         return flag[s.length()];
16     }
17 }