如何做正规的采集网站,东莞外贸网站,长春火车站到吉大一院,网站首眉怎么做给你一个字符串 s#xff0c;请你将 s 分割成一些子串#xff0c;使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1#xff1a; 输入#xff1a;s “aab” 输出#xff1a;1 解释#xff1a;只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子…给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1 输入s “aab” 输出1 解释只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。
示例 2 输入s “a” 输出0
示例 3 输入s “ab” 输出1
提示 1 s.length 2000 s 仅由小写英文字母组成
动态规划
class Solution {
public:int minCut(string s) {int n s.size();vectorvectorbool g(n, vectorbool(n, true));for(int i n-1; i 0; i--){for(int j i1; j n; j){g[i][j] s[i] s[j] g[i1][j-1];}}vectorint f(n, INT_MAX);for(int j 0; j n; j){if(g[0][j]){f[j] 0;}else{for(int i 0; i j; i){if(g[i1][j]){f[j] min(f[j], f[i] 1);}}}}return f[n-1];}
};时间复杂度O(n^2) 空间复杂度O(n^2)
这道题最关键的部分是我们要对字符串s进行处理我们通过一个二维数组来记录字符串的各个部分是否是回文字符串。 我们定义一个二维数组g[i][j]来表示字符串[i…j]这一段是否是回文串。在检查是否是回文串的时候我们只需要判断s[i]和s[j]是否相等如果相等的话那么[i1,…,j-1]是否是回文串如果也是的话就说明g[i][j]是true。在处理回文串的时候需要注意我们要初始化g[i][j]都为true这是为了避免额外判断若初始化为 false则需要额外处理长度为 1 或 2 的子串代码的复杂度会增加。初始化为 true 可以确保所有的单字符子串都被认为是回文代码逻辑更加简洁。
预处理完字符串后我们定义一个动态数组f[i]他代表字符串[0,…,i]的最小分割次数是多少。我们先遍历j从0到n-1也就是我们要找出从 0到1,0到2,…,0到(n-1)字符串的最小分割次数是多少。因为我们最终的目的就是求从0到(n-1)的字符串的最小分割次数那么我们求0到j的最小分割次数就可以从前面的状态转换而来。
那么如何进行状态转换f[j]如何从之前计算过的状态转换而来我们这时候遍历下标i目的是判断从i1到j这字符串是否是回文如果是回文的话那么从0到j这个字符串的最小分割次数不就是0到i的最小分割次数加上1吗。然后我们不断寻找状态转换后的f[j]的最小值并记录。
最后返回f[n-1]即可。
