重庆市公司网站备案在哪了,响应式网站免费模板下载,初中生如何做网站,个人网站做哪些内容文章目录 14. 最长公共前缀解题思路#xff1a;模拟5. 最长回文子串解题思路一#xff1a;动态规划解题思路二#xff1a;中心扩散法 14. 最长公共前缀
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀#xff0c;返回空字符… 文章目录 14. 最长公共前缀解题思路模拟5. 最长回文子串解题思路一动态规划解题思路二中心扩散法 14. 最长公共前缀
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀返回空字符串 。
示例 1
输入strs [flower,flow,flight]
输出fl示例 2
输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。提示
1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成 解题思路模拟
这道题模拟的思路有两种第一种就是每次比较每个字符串同一位置的字符判断是否相等如果不相等则返回前面匹配的位置可以使用 substr() 函数直接实现这块
另一种思路就是两两字符串进行比较得到一个最长公共前缀之后将其与第三个字符串比较以此类推直到比较了所有字符串之后得到的结果就是最长的公共前缀了
两种思路的时间复杂度都是 O(n*m)其中 n 表示的是字符串的个数m 表示字符串平均字符个数下面代码我们采用的是第一种思路
class Solution {
public:string longestCommonPrefix(vectorstring strs) {// 每次比较每个字符串同一位置的字符for(int i 0; i strs[0].size(); i){char tmp strs[0][i];for(int j 1; j strs.size(); j){// 如果某个字符串越界了或者字符不相等则直接返回前面匹配的位置if((i strs[j].size()) || (strs[j][i] ! tmp))return strs[0].substr(0, i);}}return strs[0];}
};5. 最长回文子串
5. 最长回文子串
给你一个字符串 s找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同则该字符串称为回文字符串。
示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。示例 2
输入s cbbd
输出bb提示
1 s.length 1000s 仅由数字和英文字母组成 解题思路一动态规划
这道题的动态规划解法之前在学动态规划的时候就已经讲过了这里就不再赘述了具体可以参考之前的笔记
class Solution {
public:string longestPalindrome(string s) {// 定义dp二维数组dp[j][i]表示从[j, i]区间是否为回文字符串bool dp[1000][1000] { 0 };int maxlen 0, maxindex 0;for(int i 0; i s.size(); i){for(int j 0; j i; j){// 状态转移方程if(s[i] s[j]){if(i j || j 1 i)dp[j][i] true;elsedp[j][i] dp[j 1][i - 1];if(dp[j][i] i - j 1 maxlen) // 是回文字符串并且长度更长了再更新{maxlen i - j 1;maxindex j;}}}}return s.substr(maxindex, maxlen);}
};解题思路二中心扩散法
之前我们在动态规划笔记中提到字符串的常见题解方法还有一个中心扩散法至于一个马拉车算法就不讲了学习成本高使用率太低它其实借助的就是回文字符串的特性由中心自发的向外扩散寻找回文字符串直到不符合要求
假设此时我们遍历到字符串的 i 位置然后定义两个指针 left 和 right 指向该位置两指针从该位置分别向左和向右出发每次走一格判断 s[left] 是否等于 s[right]是的话说明此时就是 [left, right] 区间就是一个回文字符串则判断是否需要更新最大长度以及回文字符串的起始位置一直重复上述动作直到判断不符合或者越界了为止
但是上面操作有个问题就是只考虑到了区间是奇数的情况如果是偶数情况比如字符串 abbc 的话此时 bb 这种情况就被忽略了所以我们 需要判断偶数个字符的情况
class Solution {
public:string longestPalindrome(string s) {int n s.size();int maxlen 0, maxindex 0;for(int i 0; i n; i){// 判断奇数情况int left i, right i;while(left 0 right n s[left] s[right]){left--;right;}if(right - left - 1 maxlen){maxlen right - left - 1;maxindex left 1;}// 判断偶数情况就起始位置不一样剩下的操作逻辑都是一样的left i, right i 1;while(left 0 right n s[left] s[right]){left--;right;}if(right - left - 1 maxlen){maxlen right - left - 1;maxindex left 1;}}return s.substr(maxindex, maxlen);}
};
