递归地在Python中查找矩阵a中最长的字符串

Question

我想用递归找到给定矩阵中最长的字符串（最重复的字符）。用户给出的输入是矩阵，以及递归的起始位置。另一件事是矩阵的每个元素只能被递归函数“检查”一次。在

下面是一个例子：

如果我的矩阵是这样的：

abcdeaab
adfdgagh
madafaff
abaacafr

结果应该是start=(5,0), stop=(5,4), c='a'。结果是这样的，因为字符“a”是矩阵中最长的字符串，从位置（5,0）开始，到（5,4）结束。如您所见，矩阵必须在水平方向和垂直方向上进行检查。在

我以前并没有真正使用递归，所以我被困在这里。在

我读过这篇文章：http://interactivepython.org/courselib/static/pythonds/Recursion/recursionsimple.html。我明白为了实现我想要的目标，我的程序必须遵守三个递归定律：

• 递归算法必须有基本情况。在
• 递归算法必须改变其状态并朝着基本情况移动。在
• 递归算法本身必须递归调用。在

我开始写代码，然后走到这里：

^{pr2}$

我的程序（目前）所做的是将一个字符串转换成一个矩阵，并创建另一个称为matrix2的矩阵，它将跟踪搜索（递归）函数从矩阵访问的元素。在

如有任何建议，我们将不胜感激。在

Answer 1

首先，这个问题很难解决，而且没有已知的有效的解决方案，它被称为Longest Path Problem

要从一个单元格中找出最长路径，可以使用DFS来求解它，这是一种递归算法。在

类似Python的伪代码：

DFS((x,y),visited):
   maxPathLength = -1
   for each neighbor (x1,y1) of (x,y):
        #skip visited nodes, or nodes that are not the same character:
        if (x1,y1) in visited of arr[x][y] != arr[x1][y1]:
           continue
        #node is not visited and same character.
        #mark it as visited:
        visited.add((x1,y1))
        #recurse and store what the longest path found by recursion:
        currLength = DFS((x1,y1),visited)
        #set the max out of all paths:
        maxPathLength = max(maxPathLength, currLength)
   #clean up
   visited.remove((x,y))
   #return an answer:
   return maxPathLength  + 1

以下是递归算法的3点，因为：

• 代码中的stop子句：如果没有“unvisited”节点，则 算法将在不调用递归调用的情况下返回0。在
• 该算法改变被访问节点的状态，并移动到下一个邻居，直到没有可能的路径留下，这将是stop子句。在
• 对于当前单元的每个可能的“邻居”，该算法递归地调用自己。在

此算法将从某个源单元获得最长路径。您可以对所有单元格重复此操作，以找到“全局”最长路径。在

这个算法只提供最长路径的长度，但是通过返回一个元组(length,list)-其中list是在该路径中访问的单元，所以很容易修改它来记住路径本身。在