這題會給一個目標字串
還有一個叫做...字典，裡面包含一堆字串
如果說目標字串可以用字典裏面的字串組成的話，那就回傳true，否則就回傳false
另外字典裡的字串是不會重複的，然後字典裡的字串也可以重複使用
舉例來說：
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because"leetcode"can be segmented as"leet code".
或是：
Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because"applepenapple"can be segmented as"apple pen apple". Note that you are allowed to reuse a dictionary word.
但如果像底下這樣就不算：
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false
Sol：
這題乍看之下好像有點簡單
只要比對目標字串，如果在字典裡有找到合適的字串，就把index移過去繼續找，如果有找完就算成功啊
...大概只有我這種頭腦簡單的人才會這樣想
如果是這樣的話，可能會有一種情況就是... 明明是有解的，但是卻判斷是無解的
不信邪的可以去試試...沒錯我試過= =
這邊就不解釋了
所以這題呢，理論上每個位置每種可能都要算出來，才能得出最後的結論
問題就在於要怎麼樣省去那些不必要的計算，比如說某個位置根本就不可能有解，我們就不必算了
另外還有記錄下已經算出的結果... 看到這邊已經有點想法了
沒錯... 就是利用Dynamic Programming的技巧
code大概可以寫成底下這樣：
bool wordBreak(string s, vector<string>& wordDict) {
bool dp[s.size() + 1]; // 建立一個大小為s.size() + 1的陣列，記錄從0到那個位置是否能夠被字典裡的字串組成
dp[0] = true; // 第0個絕對是ok的，因為根本沒有字，其餘初始為false
for (int i = 1; i <= s.size(); ++i)
{
dp[i] = false;
}
for (int i = 0; i < s.size(); ++i) // 開始計算每個位置
{
if (dp[i] == false) // 如果從0到i這個位置根本就沒辦法被組成，表示也沒有接著算的必要
{
continue;
}
for (auto &word : wordDict) // 從字典裡一個一個拿字串出來比對
{
if (s.find(word, i) == i) // 如果有找到可以接下去的字串，表示從 0~(i + word.size()) 是可以被組成的，把它設為true
{
dp[i + word.size()] = true;
}
}
}
return dp[s.size()]; // 最後只要看最後那個位置是否能被組成，就是答案了
}
其實只要掌握一點訣竅，這類型的題目似乎都是差不多的作法
差別可能只在於要記錄什麼，以及計算的條件之類的
之前也有寫過幾題類似的，有興趣或是忘記可以回去翻一下
那這題就這樣了~ 一日至少一題~ 繼續加油~
留言列表
