LeetCode ---- 5. 最长回文子串 (java)

方法一暴力求解时间复杂度O(n^3)暴力法将选出所有子字符串可能的开始和结束位置并检验它是不是回文。空间复杂度O(1)class Solution { public String longestPalindrome(String s) { String maxS new String(); for(int i 0; is.length(); i){ for(int j s.length() - 1; j i; j--){ if(maxS.length() j - i 1){ break; } if(isPalindrome(s.substring(i,j1))){ if(s.substring(i,j1).length() maxS.length()){ maxS s.substring(i,j1); } } } } return maxS; } public boolean isPalindrome(String s){ int len s.length(); for(int i 0; i len/2; i){ if(s.charAt(i) ! s.charAt(len -1 -i)){ return false; } } return true; } }方法二参考链接https://www.acwing.com/solution/LeetCode/content/51/暴力枚举 O(n^2)由于字符串长度小于1000因此我们可以用 O(n^2)的算法枚举所有可能的情况。首先枚举回文串的中心 i然后分两种情况向两边扩展边界直到遇到不同字符为止:回文串长度是奇数则依次判断 s[i−k]s[ik],k1,2,3,…回文串长度是偶数则依次判断 s[i−k]s[ik−1],k1,2,3,…如果遇到不同字符则我们就找到了以 i 为中心的回文串边界。时间复杂度分析一共两重循环所以时间复杂度是 O(n^2)。c:class Solution { public: string longestPalindrome(string s) { int res 0; string str; for (int i 0; i s.size(); i ) { for (int j 0; i - j 0 i j s.size(); j ) if (s[i - j] s[i j]) { if (j * 2 1 res) { res j * 2 1; str s.substr(i - j, j * 2 1); } } else break; for (int j i, k i 1; j 0 k s.size(); j -- , k ) if (s[j] s[k]) { if (k - j 1 res) { res k - j 1; str s.substr(j, k - j 1); } } else break; } return str; } }; 作者yxc 链接https://www.acwing.com/solution/LeetCode/content/51/ 来源AcWing 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。用dp[i][j]表示子串 i 到 j 是否是回文使用动态规划求解string longestPalindrome(string s) { int m s.size(); if (m 0) { return ; } vectorvectorint dp(m, vectorint(m, 0));//创建m*m数组 int start 0; int length 1; for (int i 0; i m; i) { //初始化初始状态 // 单个字符属于回文例如 abcd dp[i][i] 1; // 连续两个字符相同属于回文例如 abb if (i m - 1) { if (s[i] s[i 1]) { dp[i][i 1] 1; start i; length 2; } } } for (int len 2; len m; len) { for (int i 0; i m - len; i) { int j i len; // 扩展长度 if (dp[i 1][j - 1] 1 s[i] s[j]) { dp[i][j] 1; if (j - i 1 length) { start i; length j - i 1; } } } } return s.substr(start, length); }