leetcode筆記：Word Break

leetcode筆記：Word Break

一. 題目描述

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

二. 題目分析

如果使用遞歸，會超時。這時使用動態規劃即可解決問題，即將源字符串s從開始到結尾，分解成各個子串進行操作，對於這類字符串組合問題，需要掌握類似狀態轉移方程。對於下標i所對應字符的匹配狀態flag[i]，如果dict有字符串可以匹配，這取決於之前某個字符j的狀態出現匹配，且從數組s的j + 1到i下標之間的字符也能從dict中找到匹配的字符串：

flag[i] = any(flag[j] && (s[j + 1, i] ∈ dict))

三. 示例代碼

class Solution
{
public:
    bool wordBreak(string s, unordered_set &dict) 
    {
        vector wordFlag(s.size() + 1, false); // 動態規劃
        wordFlag[0] = true;
        for (int i = 1; i < s.size() + 1; ++i)
        {
            for (int j = i - 1; j >= 0; --j)
            {
                if (wordFlag[j] && dict.find(s.substr(j, i - j)) != dict.end())
                {
                    wordFlag[i] = true;
                    break;
                }
            }
        }
        return wordFlag[s.size()];
    }
};

四. 小結

動態規劃對於解決一些字符串的問題也是有效且容易實現的。