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

1，单词拆分

1.1，题目解析

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

1.2，思路

利用动态规划解题

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

1.3，代码

代码语言：javascript

AI代码解释

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，代码

代码语言：javascript

AI代码解释

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，代码

代码语言：javascript

AI代码解释

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]; } };