**
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:
這次作業(yè)是挺帶勁的置鼻。因?yàn)槲覜]有做出來勺届。。后來一查，恩，是Medium。那就不難過啦。
說實(shí)話价卤，這次作業(yè)還是做出來的。但是用的遞歸渊涝，用時(shí)過長了慎璧，就測試不出來了。
然后我就看了網(wǎng)上大神寫的代碼跨释。沒話說炸卑。怎么總結(jié)呢？總結(jié)不出來煤傍。這就是一種想法。按我說嘱蛋，就是步步為營蚯姆，并且，同時(shí)洒敏，保證不會重復(fù)判斷之前已經(jīng)判斷過的情況龄恋。我看了網(wǎng)上評論，說這東西就是 dynamic programming. 實(shí)在太累了凶伙。明天回來一定好好查下郭毕，然后總結(jié)到這里。
然后函荣，展示下我自己寫的遞歸版代碼：
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;
}
}
這個(gè)遞歸我覺得寫得還是挺不錯(cuò)的显押。為什么會超時(shí)呢？很明顯傻挂，因?yàn)橛泻芏嗲闆r乘碑，我之前已經(jīng)判斷過了，之后會繼續(xù)重復(fù)判斷金拒。所以必須要設(shè)標(biāo)志位來避免重復(fù)判斷兽肤。
**
總結(jié)：
Dynamic Programming:網(wǎng)上又叫做，動態(tài)規(guī)劃绪抛。我不是很理解资铡。明天上網(wǎng)查了再說。
**
說好的一天至少一道題目幢码。今天別看我現(xiàn)在凌晨2:43才提交笤休。其實(shí)23:30就寫好了。
今天早上就去了學(xué)校復(fù)習(xí)蛤育。然后對C++有了更深層次的理解宛官。
這個(gè)也是明天必須得總結(jié)的葫松。如何用C來實(shí)現(xiàn)面向?qū)ο缶幊獭Ｆ鋵?shí)C中就含有向上轉(zhuǎn)型和向下轉(zhuǎn)型的特點(diǎn)底洗，就是結(jié)構(gòu)體指針和void指針的配合腋么。
然后，我也終于明白了模板和繼承是完全不同的亥揖。比如珊擂，模板是靜態(tài)的，是編譯時(shí)候完成的费变。而繼承是動態(tài)的摧扇，是運(yùn)行時(shí)候動態(tài)綁定的。明天總結(jié)挚歧。
一個(gè)小疑問扛稽，如果誰正好看到了這篇文章，又正好懂滑负，萬望求教在张。
**
Java中是不是只有繼承，沒有模板這種概念矮慕？模板是不是函數(shù)編程特有的概念帮匾？
**
C++復(fù)習(xí)剩下的就是一塊自己一直很懂的地方，函數(shù)式編程痴鳄。
所以明天也得查一下什么叫做函數(shù)編程瘟斜，還有 λ-expression.
然后今天學(xué)習(xí)了電氣上面的一些知識。覺得好牛逼痪寻。螺句。。power application 原來也已經(jīng)和計(jì)算機(jī)緊密結(jié)合到這個(gè)地步了槽华。
單相不可控整流器
三相不可控整流器
單相可控整流器
三相可控整流器
overlap現(xiàn)象壹蔓。。猫态。佣蓉。
這些就不總結(jié)了。感覺還是挺牛逼的亲雪。
明天總結(jié)下勇凭，
動態(tài)規(guī)劃，函數(shù)編程义辕，模板和繼承虾标，C實(shí)現(xiàn)面向?qū)ο蟆?/p>
累死了累死了」嘧回來寫代碼到23:30璧函，又接著寫報(bào)告到現(xiàn)在傀蚌。每次交報(bào)告，都是看出人性劣根性的最好機(jī)會蘸吓。有些人就想混善炫，比如我。有些人就是不肯給库继。有些人不肯給但又不想直接表現(xiàn)出來箩艺，就會采取各種方式搪塞過去。
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];
}
}
這個(gè)是DP的解法宪萄。復(fù)雜度是 O(n ^ 2)
然后發(fā)現(xiàn)還有種解法是 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
每個(gè)節(jié)點(diǎn)都是在string s 中的 position, 邊是 dictionary 里面的string
如果position0 + word1 --> position5
那么就是兩個(gè)結(jié)點(diǎn)艺谆，0 and 5,中間有一條邊，就是這個(gè)word
這道題目讓我想起了另外一道題目: Jump game
但是不同拜英。
那道題目静汤， nums[i] + i 是下一步可以達(dá)到的最大位置，但是在這個(gè)位置之前的位置居凶，也都是可以達(dá)到的撒妈。
而這道題目，在這之前的位置排监，并不能達(dá)到。
所以這道題目可以用BFS來解杰捂，而Jump game 不行舆床。
另外，對已經(jīng)確定可以達(dá)到的結(jié)點(diǎn)嫁佳，把他們放入set中挨队，這樣以后就不會重復(fù)加入到隊(duì)列里面去導(dǎo)致重復(fù)訪問了。
Anyway, Good luck, Richardo! -- 09/05/2016
