码字仓颉

寻找最长回文字符串

2018-04-16

寻找最长回文字符串

1. 问题描述

给定一个字符串 s，找到 s 中最长的回文子串。
示例 1：

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

示例 2：

1
2
输入: "cbbd"
输出: "bb"

2. 解决方法

2.1 暴力解法

该方法直接使用两次循环，找出所有可能的字符串组合，再去判断每个字符串是否是回文字符串。

  • 时间复杂度：O(n^3)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {string} s
 * @return {string}
 */
let longestPalindrome = function(s) {
  let len = s.length
  let result = s.slice(0, 1)
  let maxLen = 1
  for (let i = 0; i < len; i++) {
    for (let j = len - 1; j > i + maxLen - 1; j--) {
      let str = s.slice(i, j + 1)
      let reverse = str
        .split('')
        .reverse()
        .join('')
      if (str === reverse && str.length > maxLen) {
        result = str
        maxLen = result.length
      }
    }
  }
  return result
}

2.2 动态规划算法

2.3 中心扩展算法

Tags: 算法
← 解决 WFS 矢量要素重复加载问题 节流与防抖 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章