最长回文字符串的三种解法

 

先解释一下什么是回文字符串，比如说字符串“aba”，无论是从先往后读取还是从后往前读取，结果都是一样的。当给定很长的字符串时，如何快速获取到最长的回文字符串，这也是大厂比较常见的算法面试题，那么这里给出三种解法。

• 1.暴力穷举法

  思路：即遍历每种子字符串，然后判断该子字符串是否为回文(即前半部分是否等于后半部分)，时间复杂度为O(n*n*n)

/**     * 暴力穷举     * 遍历每种子字符串，然后对该子字符串进行判断是否为回文(即比较前半部分是否等于后半部分)     * @param str     */    public static String baoli(String str) {        long startTime = System.currentTimeMillis();        String res = "";        int max = 0;        int length = str.length();        if (length < 2) {            return "";        }        for (int i = 0; i < length; i++) {            for (int j = i + 1; j <= length; j++) {                String test = str.substring(i, j);                /**如果当前的子字符串比当前回文字符串的长度要小，则直接略过*/                if (isPalindromic(test) && test.length() > max) {                    res = str.substring(i, j);                    max = Math.max(max, res.length());                }            }        }        System.out.println("暴力破解法耗时:" + String.valueOf(System.currentTimeMillis() - startTime));        return res;    }​    private static boolean isPalindromic(String test) {        int length = test.length();        /**只需要遍历前半部分长度即可,*/        for (int i = 0; i < length / 2; i++) {            if (test.charAt(i) != test.charAt(length - i - 1)) {                return false;            }        }        return true;    }

• 2.中间扩散法

从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。

1.首先往左寻找与当期位置相同的字符，直到遇到不相等为止。

2.然后往右寻找与当前位置相同的字符，直到遇到不相等为止。

3.最后左右双向扩散，直到左和右不相等。如下图所示:

/**     * 中心扩散     * 思想:即从每个位置出发，向两边扩散，直到左右两边不相等结束     *     * @param str     */    public static String centerSolution(String str) {        long startTime = System.currentTimeMillis();        if (str.length() == 0 || str == null) {            return "";        }        int strLength = str.length();        String res = "";        for (int i = 0; i < strLength; i++) {            /**当str长度为奇数*/            String preid = palindrome(str, i, i);            /**当str长度为偶数*/            String preid1 = palindrome(str, i, i + 1);            res = preid.length() > res.length() ? preid : res;            res = preid1.length() > res.length() ? preid1 : res;        }        System.out.println("中间扩散法耗时:" + String.valueOf(System.currentTimeMillis() - startTime));        return res;    }​    public static String palindrome(String str, int left, int right) {        if (left <= right && str.length() > 0) {            while (left >= 0 && right < str.length() && str.charAt(left) == str.charAt(right)) {                left--;                right++;            }            /**注意:这里是左闭右开，且此时的left和right对应的字符已经不相等了,所以最后截取的下标为left+1,right-1*/            return str.substring(left + 1, right);        } else {            return "";        }    }

• 3.动态规划法

  一开始我刚听到动态规划这个词的时候感觉很高大上，后来经过查找资料发现其实很简单，只不是从下向上的计算，说白了就是空间换时间，把中间的计算结果暂存起来，避免重复计算；

  思路：

     1.我们用一个 boolean dp[i][j]表示字符串从 i 到 j 这段是否为回文。

     2.试想如果dp[i][j]=true，我们要判断 dp[i-1][j+1]是否为回文。

  只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。动态规划关键是找到初始状态和状态转移方程。

  初始状态，l=r 时，此时  dp[l][r]=true。

  状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。

   

  public static String dynamicSolution(String str) {        long startTime = System.currentTimeMillis();        if (str.length() == 0 || str == null) {            return "";        }​        int strLength = str.length();        int maxLen = 1;        int beging = 0;​        if (strLength < 2) {            return str;        }​        boolean[][] dp = new boolean[strLength][strLength];        /**初始化,字符自身就是一个回文*/        for (int i = 0; i < strLength; i++) {            dp[i][i] = true;        }        for (int r = 1; r < strLength; r++) {            for (int l = 0; l < r; l++) {                /**比较l和r下标字符是否一致*/                if (str.charAt(r) != str.charAt(l)) {                    dp[l][r] = false;                } else {                    if (r - l < 3) {                        dp[l][r] = true;                    } else {                        dp[l][r] = dp[l + 1][r - 1];                    }                }​                /**比较最大回文长度,更新信息*/                if (dp[l][r] && r - l + 1 > maxLen) {                    maxLen = r - l + 1;                    beging = l;                }            }        }        System.out.println("动态规划法耗时:" + String.valueOf(System.currentTimeMillis() - startTime));        return str.substring(beging, beging + maxLen);    }​​​