P9 最长回文子串 LeetCode5

字数统计: 626字 | 阅读时长: 2分

2019-12-17

题解后补。

题目

解题

伪代码描述（推荐）

分析及源码

Java解法一

暴力求解，列举所有的子串，判断是否为回文串，保存最长的回文串。

class Solution {
    public boolean judgePalindrome(String s) {
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }
    
    public String longestPalindrome(String s) {
        String res = "";
        int maxLength = 0;
        int len = s.length();
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j <= len; j++) {
                String testString = s.substring(i, j);
                if (judgePalindrome(testString) && testString.length() > maxLength) {
                    res = s.substring(i, j);
                    maxLength = Math.max(maxLength, res.length());
                } 
            }
        }
        return res;
    }
}

时间复杂度： O（n³）。

空间复杂度：O（1），常数个变量。

暴力解法通过案例数101/103

Java解法二

把原来的字符串倒置了，然后找最长的公共子串。

求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，

整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话

1	arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1

当 i = 0 或者 j = 0 的时候单独分析，字符相等的话

1	arr [ i ][ j ] = 1

$$
arr[i][j]
$$

保存的就是公共子串的长度。

当原始字符串S 的其他部分中存在非回文子串的反向副本时，最长公共子串法就会失败。

当找到最长的公共子串的候选项时，都需要检查子串的索引是否与反向子串的原始索引相同。如果相同，那么我们尝试更新目前为止找到的最长回文子串；如果不是，我们就跳过这个候选项并继续寻找下一个候选。

class Solution {
    public String longestPalindrome(String s) {
       if (s.equals("")) {
           return "";
       }
       String originStr = s;
       String reverseStr = new StringBuffer(s).reverse().toString();
       int length = s.length();
       int [][] array = new int[length][length];
       int maxLen = 0;
       // 记录最大回文串结尾的字符
       int maxEnd = 0;
       for (int i = 0; i < length; i++) {
           for ( int j = 0; j < length; j++) {
               if (originStr.charAt(i) == reverseStr.charAt(j)) {
                   if (i == 0 || j == 0) {
                       array[i][j] = 1;
                   } else {
                       array[i][j] = array[i - 1][j - 1] + 1;
                   }
               }
               if (array[i][j] > maxLen) {
                   int beforeRev = length - 1 -j;
                   if (beforeRev + array[i][j] - 1 == i) {
                    maxLen = array[i][j];
                    maxEnd = i;
                   } 
               }
           }
       }
       return s.substring(maxEnd - maxLen + 1, maxEnd + 1);

    }
}

时间复杂度：两层循环，O（n²）。

空间复杂度：一个二维数组，O（n²）。

本文作者： Yao Zhu
发布时间： 2019-12-17
最后更新： 2019-12-21
本文链接： https://juoyo.github.io/posts/7e6bdb80.html
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！