【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.             int j = 0; j < i; j++) {  
6.                 if (res[j] && wordDict.contains(s.substring(j, i))) {  
7.                     res[i] =                      break;  
8.                 }  
9.             }  
10.         }  
11. return res[s.length()];  
12.     }  

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!