单词拆分

LeetCode 139 · Medium · 1 min · 榎aaaa

1. 确定状态：dp[ i ] 代表前 i 个字符组成的字符串是否能够被拆分
2. 状态转移：dp[ i ] = (**dp[ j ]** && **s.substr(j, i - j)**也能够被拆分)，其中 j 为区间 [ 0, i ] 的任意整数

具体实现：

首先将字典转换为无序集合，提高查找速度；原字符串拷贝至string_view类型，以实现零开销访问范围内的部分字符串；最后定义dp数组，用来记录前 i 个字符能否被拆分，注意这里的首位元素为真，因为空字符串肯定是能够被拆分的，其他位默认为假

进入循环——外层循环遍历原字符串，内层循环遍历字典；之后根据上述的 b 条件，确定字符串前i个元素是否能拆分

 1bool wordBreak(string s, vector<string>& wordDict)
 2{
 3    std::unordered_set<string_view> dict(wordDict.begin(), wordDict.end());
 4    std::string_view sv = s;
 5    std::vector<bool> dp(s.size() + 1, false);
 6    dp[0] = true;
 7
 8    for(int i = 1; i <= s.size(); i++)
 9    {
10        for(int j = 0; j < i; j++)
11        {
12            if(dp[j] && dict.find(sv.substr(j, i - j)) != dict.end())
13            {
14                dp[i] = true;
15                break;
16            }
17        }
18    }
19    return dp[s.size()];
20}