【LeetCode】最长回文子串

刺骨的言语ヽ痛彻心扉 2023-02-14 13:03 15阅读 0赞

题目要求：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"  
输出: "bab"  
注意: "aba" 也是一个有效答案。  
示例 2：

输入: "cbbd"  
输出: "bb"

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring

网络上有了好几种解法，什么倒排的二维数组，动态规划，马拉车等，我用的是比较简单的假定中心的方法，来解决的这个问题。

回文串，意味着以中心为节点，往两边走，文字是相同的，由此，才可以使用中心法来从中间往外推算。

代码如下：

class Solution {
        public String longestPalindrome(String s) {
            if(s == null || s.trim().length() == 0){
                return "";
            }
            char[] c = s.toCharArray();
            int n = c.length;
            // 为中心游标
            int t1,t2;
            // 为回文子串标记记录
            int max = 0,start = 0,end = 0;
            // 设定中心算法
            for(int i = 0 ; i < n ; i++){
                t1 = i;
                t2 = i;
                while(t1 >= 0 && t2 < n && c[t1] == c[t2]){
                    // 如果相等，且比最大的子串还大，则取此处的
                    if(t2 - t1 > max){
                        max = t2 - t1;
                        start = t1;
                        end = t2;
                    }
                    
                    t1--;
                    t2++;
                }
                // 这里是为了应对双中心的策略也就是子串字符数为偶数
                t1 = i;
                t2 = i + 1;
                while(t1 >= 0 && t2 < n && c[t1] == c[t2]){
                    if(t2 - t1 > max){
                        max = t2 - t1;
                        start = t1;
                        end = t2;
                    }
                    t1--;
                    t2++;
                }
            }
            return s.substring(start,end+1);
        }
    }

由于之前对题目的不是很理解，所以最开始的一版代码写成了最长的首尾呼应串，即前后只要有一个字符相等的最长字符串。

于是导致了错误，代码如下：

class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.trim().equals("")){
                return "";   
            }
            char[] c1 = s.toCharArray();
            char[] c2 = new char[s.length()];
            
            int min = 0;
            int max = 0;
            int interval = 0;
            for (int i = 0; i < c1.length; i++) {
                int bookMark = findStrInArray(c2,String.valueOf(c1[i]));
                if (bookMark != -1){
                    if(i - bookMark > interval){
                        min = bookMark;
                        max = i;
                        interval = i - bookMark;
                    }
                    
                }  
                c2[i]=c1[i];
            }
            if(max > 0){
                // 输出从min 到 max的字符
                String res = "";
                for (int j = min; j <= max; j++) {
                    res += c2[j];
                }
                return res;
            }
            // 如果没有回环，默认输出第一个字符
            return String.valueOf(c1[0]); 
        }
    
        public int findStrInArray(char[] array, String target){
            if(array.length == 0){
                return -1;
            }
    
            if(target == null || target.trim().equals("")){
                return -1;
            }
    
            for (int i = 0; i < array.length; i++) {
                if(target.equals(String.valueOf(array[i])) ){
                    return i;
                }
            }
    
            return -1;
        }
    }