Leetcode139-单词划分

问题描述

解题思路

一个简单的思路是，如果单词$s[0:n]$已经确定可以拼接出，而又存在单词$s[n:m]$，那么显然$s[0:m]$是可以得到的。因此，我们只关心前半部分是否能够拼接出，而不关心是如何拼接出的，然后与已有的单词组合，将状态进行转移：

1.正向转移：用$dp[i]$表示$s[0:i]$是否能够得到，若能，则枚举所有单词匹配$s[i+1]$开始的部分，并将匹配成功的终点设置为true

代码实现

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        bool *dp = new bool [n+1]();
        dp[0] = true;
        for(int i = 0;i < n;i++)
        {
            if(!dp[i]) continue;
            for(const string & word: wordDict)
            {
                int m = word.size();
                if(i+m <= n && s.substr(i,m) == word)
                    dp[i+m] = true;
            }
        }
        return dp[n];
    }
};

复杂度

Author@Kuroko

GitHub@SuperKuroko

LeetCode@kuroko177

Last Modified: 2023-02-21 19:18