中国建设银行进不了登录网站,在线p图网页版免费,手机如何制作链接,做国学类网站合法吗回文串 1. 回文子串2. 最长回文子串3. 分割回文串 IV4. 分割回文串 II5. 最长回文子序列6. 让字符串成为回⽂串的最⼩插⼊次数 1. 回文子串
1.题目链接#xff1a;回文子串 2.题目描述#xff1a; 给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目… 回文串 1. 回文子串2. 最长回文子串3. 分割回文串 IV4. 分割回文串 II5. 最长回文子序列6. 让字符串成为回⽂串的最⼩插⼊次数 1. 回文子串
1.题目链接回文子串 2.题目描述 给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
示例 1 输入s “abc” 输出3 解释三个回文子串: “a”, “b”, “c” 示例 2 输入s “aaa” 输出6 解释6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa” 提示 1 s.length 1000 s 由小写英文字母组成 3.问题分析动态规划最核心的思想就在于拆分子问题记住过往减少重复计算。 所以这道题还是寻找相同子问题然后求解。对于在字符串中寻找回文子串在字符串中可以先确定一个字符(字符串)然后在这个字符(字符串)的两侧扩展字符如果扩展前的字符(字符串)是一个回文串并且扩展的左右两侧的字符是相同的那么扩展后的字符串就是一个回文串。这道题所求的是回文子串的数目所以需要将这个字符串中的所以子串都枚举出来寻找符合条件的数目。所以可以用一个二维dp表来表示以 i 为起始以 j 为结尾的字符串是不是回文串如果是回文串那么就给返回值的结果加1。
状态表示如上述分析用一个二维布尔类型的dp表来表示以 i 为起始以 j 为结尾的字符串是不是回文串。状态转移方程用两个for循环遍历s字符串寻找子回文串要判断以 i 为起始以 j 为结尾的字符串是不是回文串如上述所分析对于中间元素来说左右两边的元素都相同那么该字符串就为回文串首先 i 位置的元素要等于 j 位置的元素然后再判断以 i 1为起始以 j - 1为结尾的字符串是不是回文串这样一个问题就被拆分成子问题。状态转移方程为dp[i][j] dp[i 1][j - 1]还需要注意对临界情况分析因为到最后的子问题可能会有多种情况s可能为某一个字符串中的子串ij 为指向s起始和结尾的下标假设1s的长度为1个i 1,j - 1当作越界但s是一个回文串假设2s的长度为2并且 s[i] s[j]i 1,j - 1也越界s也是一个回文串假设3s的长度为3并且 s[i] s[j]i1,j-1后刚好接到假设1假设4s的长度为4i1,j-1后接到假设2所以需要对长度为1和2的子串进行判断。 即当子串的长度为1或2时若s[i]s[j]则dp[i][j] true。初始化dp表中全初始化为false。填表顺序由状态转移方程dp[i][j] dp[i 1][j - 1]可知要求 ij 位置需要知道 i 1j - 1位置的dp所以需要从下往上从做往右初始化。返回值返回dp表中所有为true的个数。
4.代码如下
class Solution{
public:int countSubstrings(string s) {int n s.size();int ret 0;vectorvectorbool dp(n, vectorbool(n));for (int i n - 1; i 0; --i) //i从下往上填写{for (int j i; j n; j) //j从左往右填写{if (s[i] s[j]){if (j - i 2)dp[i][j] true;elsedp[i][j] dp[i 1][j - 1];}//或者如下代码//if (s[i] s[j])// dp[i][j] i 1 j ? dp[i 1][j - 1] : true;if (dp[i][j])ret;}}return ret;}
};2. 最长回文子串
1.题目链接最长回文子串 2.题目描述 给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1 输入s “babad” 输出“bab” 解释“aba” 同样是符合题意的答案。 示例 2 输入s “cbbd” 输出“bb” 提示 1 s.length 1000 s 仅由数字和英文字母组成 3.题目分析这道题也是寻找所有的回文子串但求的是回文子串的最长长度所以当遇到一个回文子串时需要计算回文子串的长度然后保留最长的长度在这里保存子字符串需要子字符串的起始结尾位置还需要保存子字符串的长度再细分一下只需要子字符串的起始位置和长度即可在string类型中有一个函数substrstring substr (size_t pos 0, size_t len npos) const;返回类型为string所以只要知道最长子字符串的起始位置和长度即可。
状态表示用一个二维布尔类型的dp表来表示以 i 为起始以 j 为结尾的字符串是不是回文串。状态转移方程dp[i][j] dp[i 1][j - 1].初始化dp表中全初始化为false。填表顺序由状态转移方程dp[i][j] dp[i 1][j - 1]可知要求 ij 位置需要知道 i 1j - 1位置的dp所以需要从下往上从做往右初始化。返回值返回s中的最长子字符串。
4.代码如下
class Solution
{
public:string longestPalindrome(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));int begin 0, length 0; //记录最长子字符串的起始位置和长度for (int i n - 1; i 0; --i){for (int j i; j n; j){if (s[i] s[j]){dp[i][j] j - i 2 ? true : dp[i 1][j - 1];if (dp[i][j]) //保留最长的回文子串{int l j - i 1;if (l length){length l;begin i;}}}}}return s.substr(begin, length);}
};3. 分割回文串 IV
1.题目链接分割回文串 IV 2.题目描述 给你一个字符串 s 如果可以将它分割成三个 非空 回文子字符串那么返回 true 否则返回 false 。
当一个字符串正着读和反着读是一模一样的就称其为 回文字符串 。
示例 1 输入s “abcbdd” 输出true 解释“abcbdd” “a” “bcb” “dd”三个子字符串都是回文的。 示例 2 输入s “bcbddxy” 输出false 解释s 没办法被分割成 3 个回文子字符串。 提示 3 s.length 2000 s 只包含小写英文字母。 3.题目分析这道题首先也是寻找s字符串中的回文子串然后再在回文子串中寻找3个可以拼接s字符串的回文子串具体如何寻找寻找3个子串ij 位置表示的是由 i 到 j 为回文子串那么i位置之前和j 位置之后都是回文子串那么就可以返回true这三个位置用dp[0][i - 1]dp[i][j]dp[j 1][n - 1]表示即这三个位置的bool值都为true那么返回 true 否则返回 false 如果分割为四个子串该如何解决五个子串呢六个以及k个子串呢这个思路用的应该是深度优先遍历将每层为true的路径保存起来(比如s的下标从0到2,4,6是回文串1到…) 然后挨个遍历寻找符合题意的路径即可路径问题还没有深入学习所以就先不写具体代码了。
4.代码如下
class Solution
{
public:bool checkPartitioning(string s) {int n s.size();vectorvectorbool dp(n, vectorbool(n));for (int i n - 1; i 0; --i){for (int j i; j n; j){if (s[i] s[j])dp[i][j] j - i 2 ? true : dp[i 1][j - 1];}}for (int i 1; i n - 1; i){for (int j i; j n - 1; j){if (dp[0][i - 1] dp[i][j] dp[j 1][n - 1])return true;}}return false;}
};4. 分割回文串 II
1.题目描述分割回文串 II 2.题目描述 给你一个字符串 s请你将 s 分割成一些子串使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例 1 输入s “aab” 输出1 解释只需一次分割就可将 s 分割成 [“aa”,“b”] 这样两个回文子串。 示例 2 输入s “a” 输出0 示例 3 输入s “ab” 输出1 提示 1 s.length 2000 s 仅由小写英文字母组成 3.题目分析如上述几道题一样先确定所有的回文子串然后再回文子串中寻找最少能拼接s字符串的个数。在寻找最少能拼接s字符串的个数时又是一个dp问题如要寻找一个字符串中最小的分割次数可以转为求字符串中某一个子串的最小的分割次数所以定义一个f[i]表示s 中[0, i] 区间上的字符串最少分割的次数。然后一步一步分析如果0~i位置是回文串则f[i] 0如果不是那么就在0到i中寻找回文子串定义一个位置jj到i如果是回文子串那么0到i最小的分割次数就等于j - 1位置最小的分割次数加1即f[i] f[j - 1] 1。 最后返回f表中最后一个位置的元素。
状态表示dp[j] 表示 s 中[0, i]区间上的字符串最少分割的次数。状态转移方程f[i] min(f[i], f[j - 1] 1)。初始化f表全初始化为最大值即可。填表顺序从左往右。返回值返回f表中最后一个位置的元素。
4.代码如下
class Solution
{
public:int minCut(string s){int n s.size();vectorvectorbool dp(n, vectorbool(n));for (int i n - 1; i 0; --i){for (int j i; j n; j){if (s[i] s[j])dp[i][j] j - i 2 ? true : dp[i 1][j - 1];}}vectorint f(n, INT_MAX);for (int i 0; i n; i){if (dp[0][i]) //如果0~i是回文串则不需要拆分f[i] 0;else{//否则在j~i中寻找最小的分割次数for (int j 0; j i 1; j){if (dp[j][i])f[i] min(f[i], f[j - 1] 1);}}}return f[n - 1];}
};5. 最长回文子序列
1.题目链接最长回文子序列 2.题目描述 给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。
子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
示例 1 输入s “bbbab” 输出4 解释一个可能的最长回文子序列为 “bbbb” 。 示例 2 输入s “cbbd” 输出2 解释一个可能的最长回文子序列为 “bb” 。 提示 1 s.length 1000 s 仅由小写英文字母组成 3.题目分析这道题需要找到字符串中回文子序列子序列不一定连续遍历字符串肯定需要从某个位置到某个位置所以定义dp[i][j]表示s字符串 [i, j] 区间内的所有的⼦序列中最⻓的回⽂⼦序列的⻓度然后在ij 位置进行分析如果i j此时s[i] s[j]则回文子序列长度为1即dp[i][j] 1。如果 i 不等于 j 并且s[i] s[j]那么ij 位置的值是不是比i 1,j - 1位置的长度多2即dp[i][j] dp[i 1][j - 1] 2如果s[i] 不等于s[j]那么就在dp[i][j - 1]dp[i 1][j]中找最大的值保留即可为什么在dp[i][j - 1]dp[i 1][j]中寻找?因为i,j不是回文串(i,j-1)(i1,j)中可能是回文串也可能不是但是这两个位置存放的是最⻓的回⽂⼦序列的⻓度。因为是从下到上遍历所以最后返回dp[0][n - 1]的值。
状态表示dp[i][j]表示s字符串 [i, j] 区间内的所有的⼦序列中最⻓的回⽂⼦序列的⻓度。状态转移方程当 s[i] s[j] 时 dp[i][j] dp[i 1][j - 1] 2 当s[i] ! s[j] 时 dp[i][j] max(dp[i][j - 1], dp[i 1][j])。初始化dp表全初始化为0当 i j 时dp[i][j] 1。填表顺序从下到上从左往右。返回值返回dp[0][n - 1]的值。
4.代码如下
class Solution
{
public:int longestPalindromeSubseq(string s) {int n s.size();vectorvectorint dp(n, vectorint(n));for (int i n - 1; i 0; --i){dp[i][i] 1;for (int j i 1; j n; j){if (s[i] s[j])dp[i][j] dp[i 1][j - 1] 2;elsedp[i][j] max(dp[i 1][j], dp[i][j - 1]);}}return dp[0][n - 1];}
};6. 让字符串成为回⽂串的最⼩插⼊次数
1.题目链接让字符串成为回⽂串的最⼩插⼊次数 2.题目描述 给你一个字符串 s 每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1 输入s “zzazz” 输出0 解释字符串 “zzazz” 已经是回文串了所以不需要做任何插入操作。 示例 2 输入s “mbadm” 输出2 解释字符串可变为 “mbdadbm” 或者 “mdbabdm” 。 示例 3 输入s “leetcode” 输出5 解释插入 5 个字符后字符串变为 “leetcodocteel” 。 提示 1 s.length 500 s 中所有字符都是小写字母。 3.问题分析这道题也是从 i 位置到 j 位置进行分析先定义一个dp[i][j]表示字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数。然后对ij 位置进行分析如果s[i] s[j]那么 [i, j] 区间内成为回⽂⼦串的最少插⼊次数取决于 [i 1, j - 1] 区间内成为回⽂⼦串的最少插⼊次数 若 i j 或 i j - 1 那么 [i, j] 区间⼀定是回⽂⼦串成为回⽂⼦串的最少插⼊次数是0。此时 dp[i][j] i j - 1 ? 0 : dp[i 1][j - 1] 。如果s[i] ! s[j]那么就如上道题一样在区间(i,j-1)(i1,j)中寻找插入次数最小的此时dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1由状态转移方程可知要求dp[i][j]先要知道dp[i1][j] 和dp[i][j-1]的值所以对于i来说应该从下到上遍历对于j来说应该从左往右遍历因为是从下到上遍历所以最后返回dp[0][n - 1]的值。
状态表示dp[i][j]表示字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数。状态转移方程如果 s[i] s[j] dp[i][j] i j - 1 ? 1 : dp[i 1][j - 1] 如果 s[i] ! s[j] dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1 。初始化dp表全初始化为0。填表顺序从下到上从左往右。返回值返回dp[0][n - 1]的值。
4.代码如下
class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorint dp(n, vectorint(n));for (int i n - 1; i 0; --i){for (int j i; j n; j){if (s[i] s[j]){dp[i][j] j - i 2 ? 0 : dp[i 1][j - 1];}else{dp[i][j] min(dp[i][j - 1], dp[i 1][j]) 1;}}}return dp[0][n - 1];}
};
