我试图通过动态规划解决一个问题。我有一个字符串,我需要找到所有可能的回文子串。比如说,我有一个长度为 n
的字符串。我为查找创建了一个矩阵 n*n
。单元格 (i,j)
要么是 1,要么是 0。如果是 1,则表示子串 [i..j] 是回文,否则为 0。最初对角线为 1,因为每个字符本身就是一个回文。
我需要如上所述正确填充矩阵。
我想通了以下内容:
- 如果 substring[i..j] 是一个原语,那么我可以通过检查矩阵是否在
O(1)
时间内找到 substring[i-1..j+1] 是否是回文[i][j]==1 and word[i-1] == word[j+1]..
对于其他一般情况,我该如何填充矩阵。
非常感谢使用伪代码/语言特定实现来填充矩阵的小解释
编辑:我需要一些关于矩阵填充的方式和顺序(即对角线、水平线等)的解释。我只想通过填写这个矩阵来解决这个问题,而不是通过其他方法。我的问题不是 this 的重复问题
最佳答案
可以检查长度为1到N的回文子串。
For i from 1 to n
Mark all substring of length i is palindromic or not.
伪代码:(基于字符串数组 1)
for len=1 to n: // check string from length 1 to n
for i=1 to (n-len + 1): // substring start from 1 to (n-len+1)
j = i + len - 1
if len == 1:
matrix[i][j]==1
else if len == 2:
if array[i] == array[j]:
matrix[i][j] = 1
else:
matrix[i][j] = 0
else:
if matrix[i+1][j-1] == 1 and array[i] == array[j]:
matrix[i][j] = 1
else:
matrix[i][j] = 0
关于algorithm - 寻找所有回文子串的动态规划,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39746540/