題目難度:Medium

題目連結: Word Break

題目大綱

給定一個字串 s 和一個字串陣列 wordDict, 請你判斷是否有辦法

程式碼

解法一

這是我看完 NeetCode 影片的前半段的解題思路後想出來的解法

class Solution {
private:
    vector<int> word_len;
    int s_len;
    vector<int> dp;
public:
    void solve(string& s, int idx, vector<string>& wordDict)
    {
        if (idx >= s_len)
        {
            dp[s_len] = 1;
            return;
        }

        if (dp[idx] != -1)
            return;

        for (int i = 0; i < wordDict.size(); i++)
        {
            if (s.compare(idx, word_len[i], wordDict[i]) == 0)
            {
                solve(s, idx + word_len[i], wordDict);
                if (dp[s_len] == 1)
                    return;
            }
        }

        dp[idx] = 0;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        word_len.resize(wordDict.size(), 0);
        s_len = s.length();
        dp.resize(s_len + 1, -1);
        dp[s_len] = 0;

        for (int i = 0; i < wordDict.size(); i++)
        {
            word_len[i] = wordDict[i].length();
        }

        solve(s, 0, wordDict);
        return dp[s_len];
    }
};

解法二

NeetCode 提出的最佳解

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.length() + 1, false);
        dp[s.length()] = true;

        for (int i = s.length() - 1; i >= 0; i--)
        {
            for (string word : wordDict)
            {
                if (s.compare(i, word.length(), word) == 0)
                {
                    dp[i] = dp[i + word.length()];
                }
                if (dp[i])
                    break;
            }
        }

        return dp[0];
    }
};