**
Question:
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".
**
My code:
import java.util.Set;
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
boolean[] isBreakUp = new boolean[s.length() + 1];
isBreakUp[0] = true;
for (int i = 1; i < s.length() + 1; i++) {
for (int j = 0; j < i; j++) {
if (isBreakUp[j] && wordDict.contains(s.substring(j, i)))
isBreakUp[i] = true;
}
}
return isBreakUp[s.length()];
}
}
My test result:
这次作业是挺带劲的。因为我没有做出来。。后来一查，恩，是Medium。那就不难过啦。
说实话，这次作业还是做出来的。但是用的递归，用时过长了，就测试不出来了。
然后我就看了网上大神写的代码。没话说。怎么总结呢？总结不出来。这就是一种想法。按我说，就是步步为营，并且，同时，保证不会重复判断之前已经判断过的情况。我看了网上评论，说这东西就是 dynamic programming. 实在太累了。明天回来一定好好查下，然后总结到这里。
然后，展示下我自己写的递归版代码：
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
return this.isBreakUp(s, wordDict, 0, s.length());
}
private boolean isBreakUp(String s, Set<String> wordDict, int head, int length) {
if (head == length)
return true;
for (int i = head; i < s.length(); i++) {
if (wordDict.contains(s.substring(head, i + 1)))
if (isBreakUp(s.substring(i + 1, s.length()), wordDict, i + 1, length))
return true;
else
continue;
else
continue;
}
return false;
}
}
这个递归我觉得写得还是挺不错的。为什么会超时呢？很明显，因为有很多情况，我之前已经判断过了，之后会继续重复判断。所以必须要设标志位来避免重复判断。
**
总结：
Dynamic Programming:网上又叫做，动态规划。我不是很理解。明天上网查了再说。
**
说好的一天至少一道题目。今天别看我现在凌晨2:43才提交。其实23:30就写好了。
今天早上就去了学校复习。然后对C++有了更深层次的理解。
这个也是明天必须得总结的。如何用C来实现面向对象编程。其实C中就含有向上转型和向下转型的特点，就是结构体指针和void指针的配合。
然后，我也终于明白了模板和继承是完全不同的。比如，模板是静态的，是编译时候完成的。而继承是动态的，是运行时候动态绑定的。明天总结。
一个小疑问，如果谁正好看到了这篇文章，又正好懂，万望求教。
**
Java中是不是只有继承，没有模板这种概念？模板是不是函数编程特有的概念？
**
C++复习剩下的就是一块自己一直很懂的地方，函数式编程。
所以明天也得查一下什么叫做函数编程，还有 λ-expression.
然后今天学习了电气上面的一些知识。觉得好牛逼。。。power application 原来也已经和计算机紧密结合到这个地步了。
单相不可控整流器
三相不可控整流器
单相可控整流器
三相可控整流器
overlap现象。。。。
这些就不总结了。感觉还是挺牛逼的。
明天总结下，
动态规划，函数编程，模板和继承，C实现面向对象。
累死了累死了。回来写代码到23:30，又接着写报告到现在。每次交报告，都是看出人性劣根性的最好机会。有些人就想混，比如我。有些人就是不肯给。有些人不肯给但又不想直接表现出来，就会采取各种方式搪塞过去。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
if (wordDict.contains(s)) {
return true;
}
int n = s.length();
boolean[] flag = new boolean[n + 1];
flag[0] = true;
for (int i = 1; i < n + 1; i++) {
for (int j = 0; j < i; j++) {
if (flag[j] && wordDict.contains(s.substring(j, i))) {
flag[i] = true;
break;
}
}
}
return flag[n];
}
}
这个是DP的解法。复杂度是 O(n ^ 2)
然后发现还有种解法是 BFS
My code:
public class Solution {
public boolean wordBreak(String s, Set<String> wordDict) {
if (wordDict.contains(s)) {
return true;
}
int n = s.length();
Queue<Integer> q = new LinkedList<Integer>();
Set<Integer> isVisited = new HashSet<Integer>();
q.offer(0);
while (!q.isEmpty()) {
int currIndex = q.poll();
for (int i = currIndex + 1; i <= s.length(); i++) {
if (isVisited.contains(i)) {
continue;
}
else if (wordDict.contains(s.substring(currIndex, i))) {
if (i == s.length()) {
return true;
}
else {
q.offer(i);
isVisited.add(i);
}
}
}
}
return false;
}
}
reference:
https://discuss.leetcode.com/topic/2545/a-solution-using-bfs/5
每个节点都是在string s 中的 position, 边是 dictionary 里面的string
如果position0 + word1 --> position5
那么就是两个结点，0 and 5,中间有一条边，就是这个word
这道题目让我想起了另外一道题目: Jump game
但是不同。
那道题目， nums[i] + i 是下一步可以达到的最大位置，但是在这个位置之前的位置，也都是可以达到的。
而这道题目，在这之前的位置，并不能达到。
所以这道题目可以用BFS来解，而Jump game 不行。
另外，对已经确定可以达到的结点，把他们放入set中，这样以后就不会重复加入到队列里面去导致重复访问了。
Anyway, Good luck, Richardo! -- 09/05/2016
