題目描述
給定一個字串 s，找到 s 中最長的回文子串，你可以假設 s 的最大長度為 1000，
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案，
示例 2：
輸入: "cbbd"
輸出: "bb"
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
題解
我的題解
我的思路（暴力法）：查找所有的回文找出最長回文子串
我的做法：s的長度為0，不是回文，為1時,回文就是s本身，當s中的回文長度大于1時,回文的起始位置必定等于回文的結束位置，所以從s的起始位置開始依次查找是否存在相同的字符，如果存在，截取字串判斷是否為回文，是回文則判斷是否為目前最長的回文，如果是目前最長的回文則記錄，再依次查找下一個回文
public String longestPalindrome(String s) {
if (s.length() <= 1){
return s;
}
// 最大回文長度
int length = 0;
// 回文起始位置
int start = 0;
//回文結束位置(比實際大1,截取的時候包含頭不包含尾)
int end = 0;
for (int i = 0; i <s.length() ; i++) {
for (int j = i+1; j <s.length() ; j++) {
if (s.charAt(i)==s.charAt(j)){
String str = s.substring(i,j+1);
if (huiwen(str)&&str.length()>length){
length=str.length();
start = i;
end = j+1;
}
}
}
}
return end>start?s.substring(start,end):s.substring(0,1);
}
/**
* 判斷是否為回文
* @param s
* @return
*/
private static boolean huiwen(String s){
for (int i = 0; i <s.length()/2.0 ; i++) {
if (s.charAt(i)!=s.charAt(s.length()-i-1)){
return false;
}
}
return true;
}
小插曲：代碼寫完了自測了一下通過了，那叫一個高興啊，又解決一題，趕緊去提交代碼，一提，不通過，啥？還有bug？，我再瞅瞅，嗯？超出時間限制了，有這么慢嗎？再提一下，通過了，但是要1477ms，不過這種方法的確不好，時間復雜度為O(n^3)，增長很快，來看一看官方題解是怎么做的吧！
官方題解
官方題解給了多種解題思路，其中暴力法也囊括其中（這大概是最容易想到的吧），下面只講兩種方法
1.動態規劃法
思路：
public String longestPalindrome1(String s) {
int n = s.length();
String res = "";
boolean[] P = new boolean[n];
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= i; j--) {
P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
if (P[j] && j - i + 1 > res.length()) {
res = s.substring(i, j + 1);
}
}
}
return res;
}
復雜度:
時間復雜度： O(n2），
空間復雜度： O(n ) ，
官方并沒有給代碼,代碼從精選題解中找出來的,并且進行了優化空間復雜度,不是很能看懂的建議自己去看,題目描述里面有鏈接
2.擴展中心法
思路:
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
復雜度:
時間復雜度：O(n2）
空間復雜度：O(1）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/139964.html
標籤：其他
上一篇：長跑排名預測
下一篇：C語言遞回之對稱二叉樹