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".

题解：

/*
    题意：
    给定一个字符串和词典。输出字符串是否能被分割成一个或多个词典中包含的单词。
    
    思路：
    1.原问题满足：
        * 最优子结构：问题（s是否可以拆分成多个单词）可以分解为其每个子串是否能拆分为多个单词，如果每个子串都能拆分，则原串也能被拆分。
        * 重叠子问题：有一些串会被反复计算是否能拆分
    2.动态规划
    3.递推关系式：
        f(i)表示前i个字符组成的字符串能否拆分成单词
        f(i) = f(j) && f(j+1,i) 0<=j<i<=length
*/
#include<unordered_set>
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set<string> &dict) {
        int length = s.length();
        //dp[i]表示前i个字符可被拆分成单词
        vector<bool> dp(length + 1);
        dp[0] = true;
        for (int pos = 0; pos <= length; pos++) {
            for (int i = pos + 1; dp[pos] && i <= length; i++) {
                if (dict.find(s.substr(pos, i - pos)) != dict.end()) {
                    dp[i] = true;
                }
            }
        }
        return dp[length];
    }
};