首页 > 代码库 > 139. Word Break
139. 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"
.
链接: http://leetcode.com/problems/word-break/
6/11/2017
自己做的brute force DFS超时了
注意,到今天为止leetcode的testcase不全,有可能会放过错误的代码,用这个testcase试一下
"cdbbbbbaaa"
["cdb","bbb", "cdbb", "aaa"]
官方讲解
https://leetcode.com/articles/word-break/
自己准备做一下BFS和DP
BFS
注意的问题:
1. i的意思其实是end position,第19行应该是<= s.length(),原因是当前的end有可能被放入queue作为下一次的起点,并且substring(start, end)是不包括end位置上的char的
2. 第14, 15行可以早点退出函数
1 public class Solution { 2 public boolean wordBreak(String s, List<String> wordDict) { 3 Set<String> set = new HashSet<String>(wordDict); 4 Queue<Integer> queue = new LinkedList<Integer>(); 5 boolean[] visited = new boolean[s.length()]; 6 7 queue.add(0); 8 while (!queue.isEmpty()) { 9 int start = queue.poll(); 10 if (!visited[start]) { 11 for (int i = start + 1; i <= s.length(); i++) { 12 if (set.contains(s.substring(start, i))) { 13 queue.add(i); 14 if (i == s.length()) { 15 return true; 16 } 17 } 18 } 19 visited[start] = true; 20 } 21 } 22 return false; 23 } 24 }
DP留给之后
更多讨论
https://discuss.leetcode.com/category/147/word-break
139. Word Break