LeetCode-139-單詞拆分
題目描述：給定一個(gè)非空字符串 s 和一個(gè)包含非空單詞的列表 wordDict，判定 s 是否可以被空格拆分為一個(gè)或多個(gè)在字典中出現(xiàn)的單詞。
拆分時(shí)可以重復(fù)使用字典中的單詞。
你可以假設(shè)字典中沒有重復(fù)的單詞。
示例說明請(qǐng)見LeetCode官網(wǎng)。
來源：力扣（LeetCode） ??
鏈接：https://leetcode-cn.com/problems/word-break/ ??
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
解法一：窮舉法
使用窮舉+遞歸的方式求解，效率較低，具體處理過程如下：
如果當(dāng)前字符串為null或者為空字符串，則默認(rèn)可以由字符串字典切分，直接返回true；
否則，遍歷字符串字典中的字符串：
如果某個(gè)字符串剛好和當(dāng)前字符串相等并且長(zhǎng)度一致，則直接返回true；
如果某個(gè)字符串和當(dāng)前字符串相等但是長(zhǎng)度不一致，遞歸判斷后面的字符串并返回判斷的結(jié)果。
最后，返回最終判斷的結(jié)果。
解法二：動(dòng)態(tài)規(guī)劃
首先，初始化字符串字典到哈希表wordDictSet中，便于快速查找；
然后初始化一個(gè)dp數(shù)組，數(shù)組的長(zhǎng)度為原始字符串的長(zhǎng)度加1，并初始化數(shù)組的第一個(gè)元素為true；
然后遍歷字符串，判斷從0到i的字符串是否可以由字符串字典切分而成：
判斷邏輯是從0到j(luò)的字符串可以由字符串字典切分（這個(gè)根據(jù)前面的計(jì)算得到） 并且 從j到i 的字符串在字符串字典中。
最終，返回dp數(shù)組的最后一個(gè)元素即為最終結(jié)果。
【每日寄語】 要相信機(jī)會(huì)總是會(huì)有的，不要和自己較勁，要順勢(shì)，像太極推手一樣，順勢(shì)而為，要學(xué)會(huì)利用周邊資源。
