递归地找到矩阵 a 中最长的字符串 - Python

Question

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

所以这是一个例子：

如果我的矩阵是这样的：

abcdeaab
adfdgagh
madafaff
abaacafr

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

我以前并没有真正使用过太多的递归，这就是我卡在这里的原因。

我已阅读此处的文章：http://interactivepython.org/courselib/static/pythonds/Recursion/recursionsimple.html。我明白为了达到我想达到的目的，我的程序必须遵守递归三定律：

递归算法必须有一个基本情况。
递归算法必须改变其状态并向基本情况移动。
递归算法必须递归地调用自身。

我开始写代码了，到这里：

#!/bin/python2.7

#Longest string in matrix

#Given a matrix filled with letters. Find the longest string, containing only the same letter, which can be obtained by starting
#with any position and then moving horizontally and vertically (each cell can be visited no more than 1 time).


# Settings here
# -------------
string_matrix = """
abcdeaab
adfdgagh
madafaff
abaacafr
"""
pos = (0,0)
# -------------

rows = 0
columns = 0
matrix = []
matrix2 = []


def stop():
    for l in matrix2:
        for c in l:
            if c == '1':
                return True
    return False

def search(pos):
    # my base case
    if stop():
        return

    global matrix2
    # matrix2 keeps track of the visited elements of matrix
    matrix2[pos[0]][pos[1]] = 1



def main():
    # create the matrix from string
    string_matrix_l = string_matrix.strip()
    splited = string_matrix_l.split('\n')

    global rows
    global columns
    global matrix
    global matrix2

    rows = len(splited)
    columns = len(splited[1])

    # initialize matrix with 0
    matrix = [[0 for x in range(columns)] for x in range(rows)]
    matrix2 = [[0 for x in range(columns)] for x in range(rows)]

    # print some info
    print 'Given matrix: ' + str(matrix) + '\n'
    print 'Start position: ' + str(pos)

    # set matrix from string
    i = 0
    for s in splited:
        s = s.strip()
        if s == '':
            continue

        j = 0

        for c in s:
            try:
                matrix[i][j] = c
                #print 'ok: ' + str(i) + ' ' + str(j) + ' ' +  c
            except:
                print 'fail: index out of range matrix[' + str(i) + '][' + str(j)+'] ' + c
            j = j + 1

        i = i + 1

        #print s
        #print matrix


    # get the result
    search(pos)

if __name__ == "__main__":
    main()

我的程序（目前）所做的是将字符串转换为矩阵，并创建另一个矩阵，称为 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 点，因为：

代码中的停止子句：如果没有"unvisited"个节点，则算法将 return 0 而不调用递归调用。
算法改变被访问节点的状态，并移动到下一个邻居，直到没有可能的路径，这将是停止子句。
算法针对当前单元格的每个可能 "neighbor" 递归调用自身。

此算法将为您提供从某个源单元格开始的最长路径。您可以对所有单元格重复此操作以找到 "global" 最长路径。

此算法仅提供最长路径的长度，但通过 returning 元组很容易修改它以记住路径本身(length,list) - 其中 list 是在此路径中访问的单元格。

递归地找到矩阵 a 中最长的字符串 - Python

Find the longest string in matrix a, recursively - Python

python

algorithm

recursion

vector

matrix