如何找到矩阵中最大的回文平方

Question

我正在尝试解决一个问题，我得到一个 nXn 字符方阵，我想从中找出最大回文方阵的大小？最大的回文正方形是，所有行和所有列都是回文的正方形。

例如。输入

a g h j k
s d g d j
s e f e n
a d g d h 
r y d g s

输出将是：

对应中间的正方形。我正在考虑动态规划解决方案但无法制定递归关系。我认为尺寸应该是 a(i,j,k)，其中 i、j 是矩形的右下角，k 是回文正方形的大小。有人可以帮我解决这个问题的递归关系吗？

编辑：

n<500，所以我相信我不能超过 O(n^3)。

Answer 1

让我们从验证回文的复杂性开始：

可以在 O(k) 中识别回文，其中 k 是回文的长度 see here

然后您需要对内部正方形中的每一行和每一列进行一次该测试 2k 次。 (以回文k的长度为维度)

所以现在你有 k * 2k -> O(2k^2) -> O(k^2)

然后您想将可能的搜索 space 增加到整个数据集 nxn 这是引入第二个变量的时候

您将需要在嵌套循环中迭代列 1 to (n-k) 和所有行 1 to (n-k)。

所以现在你有 (n-k)^2 * O(k^2) -> O(n^2 * k^2)

注意：此问题取决于多个变量

这与我建议您编写解决方案的方法相同，从小处着手，逐步扩大

Answer 2

我确定可能有更好的方法，而且我很确定我的逻辑是正确的，所以请按表面价值考虑，因为它未经测试。

为了简化示例，我打算说 i,j 是左上角或坐标 1,1

  1 2 3 4 5 6 7 8
1 a b c d e f g f 
2 d e f g h j k q 
3 a b g d z f g f 
4 a a a a a a a a

即(1,1) = a, (1,5) = e and (2,1) = d

现在，您可以从检查第 k 列开始，而不是检查每一列

即当k=3

1) 创建一个字符大小的二维布尔数组 table 所有结果 TRUE

2) 我首先检查第 3 列 cfg，它不是回文，因此我不再需要测试第 1 列或第 2 列。

3) 因为回文测试失败将二维数组 (1,3) 中的相应结果标记为 FALSE（我知道不要测试任何使用此位置的范围，因为它不是回文）

4) 接下来检查第 6 列，fjf 这是回文，所以我返回并测试第 5 列，ehz != 回文

5) 设置 (1,5) = 假

6) 然后测试第 8 列，然后是第 7 列，

注意：您只需测试 8 列中的 5 列。

因为一行中有k列是回文，现在测试对应的行。在这种情况下从底行开始 3 因为如果失败，它将消除大多数其他检查

7) 检查从 (3,6) 开始的行 fgf = palindrome

8) 检查从 (2,6) 开始的行 jkq != a palindrome

9) 设置 (2,6) = 假

10) 检查从 (2,3) daa 开始的列 != palindrome

11) 设置 (2,3) = 假

不需要再测试第 2 行，因为 (2,3) 和 (2,6) 都是假的

希望你能理解这一点。

注意：您可能会从 k = n 开始并递减 k 直到找到结果

Answer 3

假设您可以解决以下问题：

结束于单元格(i, j)是否有水平和垂直长度不同的回文。

以上问题提示：

   boolean[][][]palindrome;//Is there any palindrome ending at (i , j) has length k
   for(int i = 0; i < n; i++){
       for(int j = 0; j < n; j++){
           palindrome[i][j][0] = true;
           palindrome[i][j][1] = true;
           for(int k = 2; k <= n; k++)
               if(data[i][j - k + 1] == data[i][j] && palindrome[i][j - 1][k - 2])
                  palindrome[i][j][k] = true; 
       } 
  }

所以，我们可以创建两个三维数组int[n][n][n]col和int[n][n][n]row。

对于每个单元格(i, j)，我们将计算长度为k、终止于单元格(0, j)、(1, j) 、 ... (i, j) 和长度为 k 的回文总数，结束于单元格 (i,0), (i, 1), ... (i, j)

for(int k = 1; k <= n; k++)
    if(there is palindrome length k horizontally, end at cell (i, j)) 
       row[i][j][k] = 1 + row[i - 1][j][k];
    if(there is palindrome length k vertically, end at cell (i, j)) 
       col[i][j][k] = 1 + col[i][j - 1][k];

最后，if row[i][j][k] >= k && col[i][j][k] >= k -> 有一个正方形回文长度 k 结束于 (i,j)。

总的来说，时间复杂度为O(n^3)

如何找到矩阵中最大的回文平方

How to find largest square of palindrome in a matrix

algorithm

language-agnostic

dynamic-programming