【Leetcode】Word Break

题目链接：https://leetcode.com/problems/word-break/

题目：

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

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

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

思路：

res[i] = res[j]&wordDict.contains(s.subString(j,i))；

从0~i的字符串能用单词表示 取决于 是不是存在从0~j的字符串能用单词表示，且从j~i是1个单词。j<i

算法：

1. public boolean wordBreak(String s, Set<String> wordDict) {  
2.         boolean res[] = new boolean[s.length() + 1];// 表示到i为止的子串能否用单词表示  
3.         res[0] = true;  
4.         for (int i = 0; i <= s.length(); i++) {  
5.             for (int j = 0; j < i; j++) {  
6.                 if (res[j] && wordDict.contains(s.substring(j, i))) {  
7.                     res[i] = true;  
8.                     break;  
9.                 }  
10.             }  
11.         }  
12.         return res[s.length()];  
13.     }  

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠