首页 > 代码库 > 139. Word Break

139. Word Break

2024-10-04 18:45:01   214人阅读

题目：

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


联系
我们