【日常刷题/动态规划C++]单词拆分，回文子串，分割回文串2

用户11719958

发布于 2025-12-30 14:27:28

820

1，单词拆分

1.1，题目解析

判断一个字符串s，是否由给定的字典中的单词拼接而成。

1.2，思路

利用动态规划解题

最后，返回值，返回dp表最后一个值，表示以字符串最后一个字符结尾，是否可以拼接成功。

1.3，代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> hash;
        for(auto& str:wordDict)
        {
            hash.insert(str);
        }

        int n=s.size();
        vector<bool> dp(n+1);
        s=" "+s;
        dp[0]=true;

        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

2，回文子串

2.1，题目解析

找到字符串s的回文子串的个数，单个字符也算一个回文字串。

2.2，思路

2.3，代码

class Solution {
public:
    int countSubstrings(string s) {
       int n=s.size();
       vector<vector<bool>> dp(n,vector<bool>(n));
       int sum=0;

       for(int i=n-1;i>=0;i--)
       {
        for(int j=i;j<n;j++)
        { 
            if(s[i]==s[j])
            dp[i][j]=i+1<j?dp[i+1][j-1]:true;
            if(dp[i][j])
            sum++;
        }
       }
       return sum;
    }
};

3，分割回文串2

3.1，题目解析

给定的字符串s，将s分割成一些子串，使每一个子串都是回文串的最小分割次数。

3.2，思路

3，代码

class Solution {
public:
    int minCut(string s) {
        int n=s.size();
        //[i,j]区间是否为回文串
        vector<vector<bool>> dp(n,vector<bool>(n));
        for(int i=n-1;i>=0;i--)
        {
            for(int j=i;j<n;j++)
            {
                if(s[i]==s[j])
                dp[i][j]=i+1<j?dp[i+1][j-1]:true;
            }
        }

        //[0,i]区间的最少分割次数
        vector<long long> dp2(n,INT_MAX);
        for(int i=0;i<n;i++)
        {
           if(dp[0][i])
           dp2[i]=0;
           else
           {
            for(int j=1;j<=i;j++)
            {
                if(dp[j][i])
                dp2[i]=min(dp2[j-1]+1,dp2[i]);
            }
           }
        }

        return dp2[n-1];

        
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-12-30，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串