LeetCode: 5. 最长回文子串

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Runtime: 1118 ms, faster than 5.01% of Java online submissions for Longest Palindromic Substring.
 *
 * Memory Usage: 37.2 MB, less than 94.36% of Java online submissions for Longest Palindromic Substring.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2019-07-13 11:12
 */
public String longestPalindromeBruteForce(String s) {
  if (Objects.isNull(s) || s.length() == 1) {
    return s;
  }
  int maxLength = 1;
  int begin = 0;
  for (int i = 0; i < s.length() - 1; i++) {
    for (int j = i + 1; j < s.length(); j++) {
      // 这里要注意：先判断长度，然后执行回文判断，相当于做了剪枝操作，效率会提高很多。
      if (j - i + 1 > maxLength && isPalindrome(s, i, j)) {
        maxLength = j - i + 1;
        begin = i;
      }
    }
  }
  return s.substring(begin, begin + maxLength);
}

private boolean isPalindrome(String s, int low, int high) {
  while (low <= high) {
    if (s.charAt(low) != s.charAt(high)) {
      return false;
    }
    low++;
    high--;
  }
  return true;
}

public String longestPalindrome(String s) {
  if (Objects.isNull(s) || s.length() <= 1) {
    return s;
  }
  int start = 0;
  int end = 0;
  for (int i = 0; i < s.length() - 1; 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) {
  while (0 <= left && right < s.length() && s.charAt(left) == s.charAt(right)) {
    left--;
    right++;
  }
  return right - left - 1;
}

 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
43
44
45
46
47
/**
 * 自己实现
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2019-07-13 11:12
 */
public String longestPalindrome(String s) {
  if (Objects.isNull(s) || s.length() == 1) {
    return s;
  }
  int left = -1, right = -2;
  for (int i = 0; i < s.length(); i++) {
    boolean p1 = true;
    boolean p2 = true;
    for (int j = 0; j <= i; j++) {
      char c1 = s.charAt(i - j);
      // aba 型
      if (p1 && i + j < s.length()) {
        char c2 = s.charAt(i + j);
        if (c1 == c2) {
          if ((i + j) - (i - j) > right - left) {
            left = i - j;
            right = i + j;
          }
        } else {
          p1 = false;
        }
      }
      // aa 型
      if (p2 && i + 1 + j < s.length()) {
        char c2 = s.charAt(i + 1 + j);
        if (c2 == c1) {
          if ((i + 1 + j) - (i - j) > right - left) {
            left = i - j;
            right = i + 1 + j;
          }
        } else {
          p2 = false;
        }
      }
      if (!p1 && !p2) {
        break;
      }
    }
  }
  return left >= 0 ? s.substring(left, right + 1) : null;
}

 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 相仿 718 题的思路。
 *
 * TODO 解法还有少许缺陷：142个用例，通过了140个。
 *      abcdbbfcba 找不到合适的回文字符串。
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-10-08 14:22:42
 */
public String longestPalindrome(String s) {
  if (Objects.isNull(s) || s.length() == 1) {
    return s;
  }
  return findMax(s, new StringBuilder(s).reverse().toString());
}

private String findMax(String a, String b) {
  int length = b.length();
  String result = "";

  // 处理 a 的头部 与 b 的尾部 的字符串
  for (int len = 1; len <= length; len++) {
    String temp = maxLength(a, 0, b, length - len, len);
    if (temp.length() > result.length() && isPalindromic(temp)) {
      result = temp;
    }
  }
  // 由于两个字符串长度相同，则不需要处理中间对其部分的处理
  // 这里的代码假设，a 短 b 长
  // for (int i = b.length() - a.length(); i >= 0; i--) {
  //   String temp = maxLength(a, 0, b, i, a.length());
  //  }

  // 处理 a 的尾部 与 b 的头部
  for (int i = 1; i < length; i++) {
    String temp = maxLength(a, i, b, 0, length - i);
    if (temp.length() > result.length() && isPalindromic(temp)) {
      result = temp;
    }
  }

  return result.isEmpty() ? null : result;
}

private String maxLength(String a, int as, String b, int bs, int len) {
  int count = 0;
  StringBuilder temp = new StringBuilder();
  String result = "";
  for (int i = 0; i < len; i++) {
    if (a.charAt(as + i) == b.charAt(bs + i)) {
      count++;
      temp.append(a.charAt(as + i));
      if (temp.length() > result.length()) {
        result = temp.toString();
      }
    } else if (count > 0) {
      count = 0;
      temp = new StringBuilder();
    }
  }
  int sn = a.length();
  System.out.println(String.format("%3d %3d %3d  %" + (as + len != a.length() ? "-" : "")
      + sn + "s  %" + (as + len == a.length() ? "-" : "") + sn + "s" + "  %" + sn + "s",
    as, bs, len, a.substring(as, as + len), b.substring(bs, bs + len), result));
  return result;
}

private boolean isPalindromic(String s) {
  int l = 0, r = s.length() - 1;
  while (l < r) {
    if (s.charAt(l) != s.charAt(r)) {
      return false;
    }
    l++;
    r--;
  }
  return true;
}