网站用的空间,厦门网站设计培训公司,网站设计用什么软件,郑州关键词网站优化排名leetcode5
给你一个字符串 s#xff0c;找到 s 中最长的
回文串
示例 1#xff1a;
输入#xff1a;s babad
输出#xff1a;bab
解释#xff1a;aba 同样是符合题意的答案。
最开始我是将回文串都存入map。使用substr进行切割… leetcode5
给你一个字符串 s找到 s 中最长的
回文串
示例 1
输入s babad
输出bab
解释aba 同样是符合题意的答案。
最开始我是将回文串都存入map。使用substr进行切割i为起始j-i1是步长
string longestPalindrome(string s) {if (s.length() 1) {return s;}mapint,string resultmap;string temp;for (int i 0; i s.length() - 1; i) {for (int j i; j s.length(); j) { //cout temp: temp endl;string s1 s.substr(i, j-i1);temp s1;reverse(temp.begin(), temp.end());//cout s1: s1 endl;if (temp s1) {resultmap[i] s1;//cout s1: s1 endl;}}}int length 0;int index 0;for (int i 0; i resultmap.size(); i) {if (resultmap[i].length() length) {length resultmap[i].length();index i;}}return resultmap[index];
}
优化了一下还是时间复杂度高
string longestPalindrome(string s) {if (s.length() 1) {return s;}//mapint,string resultmap;string temp;int max 0;string maxstr;for (int i 0; i s.length() - 1; i) {for (int j i; j s.length(); j) { string s1 s.substr(i, j - i 1);temp s1;if (s1.length() max){reverse(temp.begin(), temp.end());//cout s1: s1 endl;//cout temp: temp endl;if (temp s1) {maxstr s1;max s1.length();//cout s1: s1 endl;}} }}return maxstr;
}
最终还是用动态规划的方式解决。动态规划的核心思想把已经发生过的情况储存起来需要时直接调用也就是空间换时间。
dp存储了某一段字符串是否是回文串dp[i][j]的值如果为true表示字符串s中从下标i到下标j的子串是一个回文串如果为false则不是回文串。
动态规划需要递推所以也需要初始化这里需要初始化单个字符串与连续字符串的情况之后递推。
string longestPalindrome(string s) {int n s.length();if (n 1) {return s;}vector vectorbool dp(n, vectorbool(n, false));for (int i 0; i s.length(); i) {dp[i][i] true;}for (int i 0; i s.length()-1; i) {if (s[i]s[i1]){dp[i][i1] true;dp[i1][i] true;}}int index0;int maxlen0;for (int len 1; len s.length(); len) {for (int j 0; j len s.length(); j) {//cout s[j] endl s[j len]endl;if (s[j] s[j len] dp[j 1][j len - 1]true) {dp[j][j len] true;dp[jlen][j] true;index j;maxlen len;cout 找到回文 :;cout index , maxlen;}}}string res s.substr(index, maxlen1);return res;
}
