題目： LeetCode - 139. Word Break

題目說明

給一個陣列及一個字串，求字串能否由陣列中的字串組成。

解題思路

使用動態規劃，dp[i] 代表前 i 個字符組成的字串可以被字典中的字串組成。先在 s 前面增加一個空格方便計算，使用一個迴圈遍歷字串，將目前遍歷到的字串分為兩個部分，若前面的部分及後面的部分都可以被組成則代表目前遍歷到的字串可以被組成。最後回傳 dp[n] 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict)
    {
        int n = s.length();
        vector<int> dp(n + 1);
        unordered_set<string> set(begin(wordDict), end(wordDict));
        s = " " + s;
        dp[0] = 1;
        for(int i = 1; i <= n; ++i) for(int j = 0; j < i; ++j)
            if(dp[j] && set.count(s.substr(j + 1, i - j))) { dp[i] = 1; break; }
        return dp[n];
    }
};