0%

回文子串算法

发表于 分类于

文章字数：359,阅读全文大约需要1分钟

回文子串指的是从前向后和从后向前读是一样的字符串，比如abba或者abcba。

暴力获取法

以下是我自己写的，思路如下：

  1. 获取可能是回文子串的字符串
  2. 判断是否是回文子串

实现是：

  1. 用一个循环遍历所有字符
  2. 再嵌套一个循环，从反方向循环，找到一样的值
    （左右相同就可能是回文子串）
  3. 判断字符串是否是回文子串，用个循环遍历其中的内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public String longestPalindrome(String s) {
        
        if (s == null || s.trim().equals("")) {
            return "";
        }

        int longsLeft = 0;
        int longsRight = 0;

        int maxLength = 0;

        char[] args = s.toCharArray();

        for (int i = 0; i < s.length() - maxLength; i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (args[i] == args[j]) {
                    if (isPalindrome(s.substring(i, j + 1))) {
                        int longs = j - i + 1;
                        if (longs > maxLength) {
                            longsLeft = i;
                            longsRight = j;
                            maxLength = longs;
                        }
                    }
                }
            }
        }

        return s.substring(longsLeft, longsRight + 1);
    }

    boolean isPalindrome(String arg) {
        char[] args = arg.toCharArray();
        for (int i = 0, j = args.length - 1; i < j; i++, j--) {
            if (args[i] != args[j]) {
                return false;
            }
        }
        return true;
    }
}

时间复杂度O(n^3)
为了直观，现将String转成char[]再操作，多占了内存。将char[]的操作改成直接操作String可以达到空间复杂度O(1)

中心扩散法

在leetcode官方讲解中看到的一个解决方法，时间复杂度O(n^2)，空间复杂度O(1)

思路：
每个回文子串都有个中心，abba的中心就是bb。abcba的中心是c。
通过中心向外扩散，即可得到整个回文子串。

实现

  1. 循环遍历每个元素（每两个）
  2. 以每个元素为中心，向两边遍历，直到不相同即为回文子串长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }