关于算法:LeetCodeGolang-647-回文子串

8次阅读

共计 3004 个字符，预计需要花费 8 分钟才能阅读完成。

给你一个字符串 s，请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过去读一样的字符串。子字符串是字符串中的由间断字符组成的一个序列。

具备不同开始地位或完结地位的子串，即便是由雷同的字符组成，也会被视作不同的子串。

示例：

输出：s = "aaa"
输入：6
解释：6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"

1 <= s.length <= 1000
s 由小写英文字母组成

本题目有两种解题思路，别离是：

枚举出所有的子串，而后再判断这些子串是否是回文；
枚举每一个可能的回文核心，而后用两个指针别离向左右两边拓展，当两个指针指向的元素雷同的时候就拓展，否则进行拓展。
官网题解中给出了从第二种思路登程的题解，咱们这篇文章次要从第一种思路登程，给出三种办法。这三种办法层层优化，从暴力解法，到应用 动静布局 的解法，再对 动静布局 进行空间上的优化。心愿可能帮忙大家了解 动静布局 的应用办法。

咱们最直观能想到的就是，枚举出所有的子串，而后再判断这些子串是否是回文。上面给出暴力解法的代码（Go）:

func countSubstrings(s string) int {// 暴力法 工夫复杂度 O(n^3)
   n := len(s)
   sum := 0
   for i := 0; i < n; i++ {
      for j := i; j < n; j++ {if isPalindromic(s, i, j) {sum++}
      }
   }
   return sum
}
func isPalindromic(s string, l int, r int) bool {
   for l < r {if s[l] != s[r] {return false}
      l++
      r--
   }
   return true
}

暴力法天然是思考难度最低的解法，置信的加都可能想到。然而咱们能够看到遍历所有子字符串须要破费 O(n^2) 的工夫，对于每个子字符串判断是否为回文须要破费 O(n) 的工夫，那么这个算法的工夫复杂度为 O(n^3)，显然对于咱们最求性能极致的程序设计师而言，这样的后果无奈承受。接下来咱们将应用 动静布局 的办法进行进一步的优化。

复杂度剖析：

工夫复杂度：O(n^3)。

空间复杂度：O(1)。额定的常数空间即可。

咱们先要找到暴力解法效率低在哪里。显然，字符串 s 的两个不同的字串 str1 和 str2 如果重叠的话，在计算过程中，重叠的子子串会执行雷同的计算逻辑，于是造成了计算的冗余。

动静布局的思维，即是存储重复子运算的后果，从而使得每个子运算只须要计算一次，是一种 工夫和空间的衡量（trade-off）。

第一步，咱们要演绎一个最优解的构造，咱们判断一个字串是回文时，一共有三种状况：

当 len(s) == 1 时，只有一个回文子串 s。
当 len(s) == 2 时，比拟 s[0]，s[1]，确定回文子串个数，2或3。
当 len(s) > 2 时，假如其子字符串 str 左端字符为 str[i] 右端字符为 str[j]，其余部分为 str(i,j)，则判断 str 是回文时，须要保障 str(i,j) 是回文且 str[i] == str[j]。

以上三点就是递归定义的判断逻辑。前两种状况作为递归的根底状况（base case）。在第三种状况中，咱们发现如果在判断另一个内容为 “AstrB”的子字符串 str2时，则咱们判断 str 是回文时，须要保障 str 是回文且 A == B。那咱们须要再次判断一次 str 是不是回文呀，不能承受！

咱们其实能够在第一次判断完 str 后果后，存储它。之后如果须要再判断 str 是否为回文时，间接返回后果，就省了很多计算内容。这就是 动静布局 了！

咱们如何存储每一个子字符串呢？一种可行的办法是，咱们搞一个 n x n 的二维布尔数组 a[i][j]，其中 i 代表子字符串的左端，j 代表子字符串的右端。就能够存储计算过的子字符串是否为回文了！

咱们在写代码的时候采纳 自下而上 的办法（具体概念参考我写过的一个对于动静布局的文章)。先贴代码（Go）:

func countSubstrings(s string) int {// 空间复杂度 O(n^2)
   n := len(s)
   sum := 0
   var a = make([][]bool, n)
   for index := 0; index < n; index++ {a[index] = make([]bool, n)
      a[index][index] = true
      sum++
      if index+1 < n && s[index] == s[index+1] {a[index][index+1] = true
         sum++
      }
   }
   for i := n - 1; i >= 0; i-- {
      for j := i + 2; j < n; j++ {if a[i+1][j-1] && s[i] == s[j] {a[i][j] = true
            sum++
         }
      }
   }
   return sum
}

首先咱们创立一个 n x n 的数组，同时初始化 base case，用于存储各子字符串的计算结果。而后在设计代码时，咱们要搞明确各个子字符串的依赖关系，如图：

假如咱们 s 是长度为 5 的字符串，则咱们创立这样的二维数组，初始化 base case。图中咱们能够看到，对于数组的每一行而言，a[n] 依赖于 a[n+1]，对于数组的每一列而言 a[n][m] 依赖于 a[n][m-1]。所以咱们须要从 base case 开始，即横坐标由大 （n-1） 到小 (0)，纵坐标由小( 以后横坐标 i + 2)到大 (n-1) 遍历。对应于子字符串则是，子字符串的开始从 s 的最右端开始，确定开始后，再由小到大的设置子字符串尾端。

依据依赖的 子子字符串的状态 以及 子字符串的开始尾端比拟，能够在 O(1) 的工夫内确定子字符串是否为回文。

复杂度剖析：

工夫复杂度：O(n^2)。遍历所有子字符串须要破费 O(n^2) 的工夫

空间复杂度：O(n^2)。须要 n x n 的辅助二维数组。

咱们再一次扫视题解三，发现他须要额定的 n x n二位数组，且该二位数组其实有一半是用不到的，这无疑是一种节约，那咱们能不能节约空间呢？答案是必定的。

通过观察咱们发现，a[n] 只依赖于 a[n+1]，那么咱们计算 a[n+1] 时能够只保留 a[n]，a[n+2] 再统计了 sum 之后则不须要再保留了。所以咱们当初只须要两个长度为 n 的数组即可。

除此之外，咱们发现，a[n][m] 也只依赖于 a[n][m-1]，也就是说对于 a[n] 的更新，是从后往前顺次更新的，那咱们能够思考，只应用一个长度为 n 的数组。在一次迭代计算 a[n][m] 时，以后 a[n][m-1] 的值实际上是上一次迭代 a[n+1][m-1] 的值，即是计算 a[n][m] 时须要的子子字符串的状态。上面是优化空间后的代码（Go）：

func countSubstrings(s string) int {// 空间复杂度 O(n)
   n := len(s)
   sum := 0
   a := make([]bool, n)
   a[0] = true
   for index := 0; index < n; index++ { 
   // index 指定数组须要解决次数，index+1 指定每次解决须要的长度
      l := n - index - 1           // l 代表字符串 s 结尾的下标
      for i := index; i > 0; i-- { // i 示意解决数组的下标，倒序解决
         if (i == 1 || a[i-2]) && s[l] == s[l+i] {
            sum++
            a[i] = true
         } else {a[i] = false
         }

      }
   }
   return sum + n
}

复杂度剖析：

工夫复杂度：O(n^2)。遍历所有子字符串须要破费 O(n^2) 的工夫

空间复杂度：O(n)。须要长度为 n 的辅助一维数组。

正文完