139. 單詞拆分

鏈接: 139. 單詞拆分

給你一個(gè)字符串 s 和一個(gè)字符串列表 wordDict 作為字典。請(qǐng)你判斷是否可以利用字典中出現(xiàn)的單詞拼接出 s 。

注意：不要求字典中出現(xiàn)的單詞全部都使用，并且字典中的單詞可以重復(fù)使用。

示例 1：

輸入: s = “l(fā)eetcode”, wordDict = [“l(fā)eet”, “code”]
輸出: true
解釋: 返回 true 因?yàn)?“l(fā)eetcode” 可以由 “l(fā)eet” 和 “code” 拼接成。
示例 2：

輸入: s = “applepenapple”, wordDict = [“apple”, “pen”]
輸出: true
解釋: 返回 true 因?yàn)?“applepenapple” 可以由 “apple” “pen” “apple” 拼接成。
注意，你可以重復(fù)使用字典中的單詞。
示例 3：

輸入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
輸出: false

1.狀態(tài)表示*
這?我們選擇?較常?的?式，以某個(gè)位置為結(jié)尾，結(jié)合題?要求，定義?個(gè)狀態(tài)表?：
dp[i] 表?： [0, i] 區(qū)間內(nèi)的字符串，能否被字典中的單詞拼接?成

2.狀態(tài)轉(zhuǎn)移方程
對(duì)于 dp[i] ，為了確定當(dāng)前的字符串能否由字典??的單詞構(gòu)成，根據(jù)最后?個(gè)單詞的起始位1置 j ，我們可以將其分解為前后兩部分：

1. i. 前??部分 [0, j - 1] 區(qū)間的字符串；
2. ii. 后??部分 [j, i] 區(qū)間的字符串。

其中前?部分我們可以在 dp[j - 1] 中找到答案，后?部分的?串可以在字典??找到。
因此，我們得出?個(gè)結(jié)論：當(dāng)我們?cè)趶?0 ~ i 枚舉 j 的時(shí)候，只要 dp[j - 1] = true
并且后?部分的?串 s.substr(j, i - j + 1) 能夠在字典中找到，那么 dp[i] =true 。

3. 初始化
可以在最前?加上?個(gè)「輔助結(jié)點(diǎn)」，幫助我們初始化。使?這種技巧要注意兩個(gè)點(diǎn)：
i. 輔助結(jié)點(diǎn)??的值要「保證后續(xù)填表是正確的」；
ii. 「下標(biāo)的映射關(guān)系」；
在本題中，最前?加上?個(gè)格?，并且讓 dp[0] = true ，可以理解為空串能夠拼接?成。其中為了?便處理下標(biāo)的映射關(guān)系，我們可以將字符串前?加上?個(gè)占位符 s = ’ ’ + s ，這樣就沒(méi)有下標(biāo)的映射關(guān)系的問(wèn)題了，同時(shí)還能處理「空串」的情況。

4. 填表順序
顯?易?，填表順序「從左往右」

5. 返回值
根據(jù)狀態(tài)表示，返回dp[n].

代碼：

bool wordBreak(string s, vector<string>& wordDict) {int n=s.size();if(n==0) return false;vector<bool> dp(n+1);s=" "+s;dp[0]=true;unordered_set<string> hash;for(auto e:wordDict){hash.insert(e);}for(int i=1;i<=n;i++){for(int j=i;j>0;j--){if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1))){//cout<<i<<" "<<j<<endl;cout<<i<<endl;dp[i]=true;break;}}//cout<<dp[i]<<endl;} return dp[n];}

467. 環(huán)繞字符串中唯一的子字符串

鏈接: 467. 環(huán)繞字符串中唯一的子字符串
定義字符串 base 為一個(gè) “abcdefghijklmnopqrstuvwxyz” 無(wú)限環(huán)繞的字符串，所以 base 看起來(lái)是這樣的：

“…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd…”.
給你一個(gè)字符串 s ，請(qǐng)你統(tǒng)計(jì)并返回 s 中有多少 不同非空子串 也在 base 中出現(xiàn)。

示例 1：

輸入：s = “a”
輸出：1
解釋：字符串 s 的子字符串 “a” 在 base 中出現(xiàn)。
示例 2：

輸入：s = “cac”
輸出：2
解釋：字符串 s 有兩個(gè)子字符串 (“a”, “c”) 在 base 中出現(xiàn)。
示例 3：

輸入：s = “zab”
輸出：6
解釋：字符串 s 有六個(gè)子字符串 (“z”, “a”, “b”, “za”, “ab”, and “zab”) 在 base 中出現(xiàn)。

1.狀態(tài)表示*
dp[i] 表?：以 i 位置的元素為結(jié)尾的所有?串??，有多少個(gè)在 base 中出現(xiàn)過(guò)。

2.狀態(tài)轉(zhuǎn)移方程
對(duì)于 dp[i] ，我們可以根據(jù)?串的「?度」劃分為兩類：

1. i. ?串的?度等于 1 ：此時(shí)這?個(gè)字符會(huì)出現(xiàn)在 base 中；

2. . ?串的?度?于 1 ：如果 i 位置的字符和 i - 1 位置上的字符組合后，出現(xiàn)在 base中的話，那么 dp[i - 1]
   ??的所有?串后?填上?個(gè) s[i] 依舊在 base 中出 現(xiàn)。因此 dp[i] = dp[i - 1] 。

綜上， dp[i] = 1 + dp[i - 1] ，其中 dp[i - 1] 是否加上需要先做?下判斷。

3. 初始化
可以根據(jù)「實(shí)際情況」，將表??的值都初始化為 1 。

4. 填表順序
顯?易?，填表順序「從左往右」

5. 返回值
?不能直接返回 dp 表??的和，因?yàn)闀?huì)有重復(fù)的結(jié)果。在返回之前，我們需要先「去重」：

1. i. 相同字符結(jié)尾的 dp 值，我們僅需保留「最?」的即可，其余 dp 值對(duì)應(yīng)的?串都可以在 最?的??找到；
2. ii. 可以創(chuàng)建?個(gè)??為 26 的數(shù)組，統(tǒng)計(jì)所有字符結(jié)尾的最? dp 值。

最后返回「數(shù)組中所有元素的和」即可。

代碼：

int findSubstringInWraproundString(string s) {int n=s.size();vector<int> dp(n,1);for(int i=1;i<n;i++){//還需要去重if(s[i]==s[i-1]+1||(s[i]=='a'&&s[i-1]=='z'))dp[i]=dp[i-1]+1;}// 計(jì)算每?個(gè)字符結(jié)尾的最?連續(xù)?數(shù)組的?度int hash[26] = { 0 };for(int i = 0 ; i < n; i++)hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);// 3. 將結(jié)果累加起來(lái)int sum = 0;for(auto x : hash) sum += x;return sum;}