如何从二维字符数组中提取对角线作为字符串

Question

我一直在尝试用编程方式解决下面的字谜，作为自己的练习:

puzzle = [
    ['t', 'r', 'o', 'l', 'l'],
    ['u', 'u', 'a', 'a', 'y'],
    ['n', 'r', 'r', 'e', 'q'],
    ['a', 'o', 'h', 'd', 'q']]
words = ["troll", "tuna", "nut", "oral", "turd", "deal", "rut", "hey", "ear"]

但是我需要一点帮助来完成这个练习。下面是我到目前为止所做的:

我将行和列转换成单个字符串，并将它们放入列表中:

a = []
#Rows
for x in puzzle:
    a.append(''.join(x))
    a.append(''.join(x)[::-1])  #Append reversed string.
#Columns
for i in range(len(puzzle[0])):
    s = ""
    for j in range(len(puzzle)):
        s += puzzle[j][i]
    a.append(s)
    a.append(''.join(s)[::-1])  #Append reversed string.

现在我可以找到任何水平或垂直拼写的单词。正如您可能已经猜到的，下一步是遍历对角线并将它们放入列表中，但只是想不出这样做的逻辑。有人能帮我一下吗?

Answer 1

首先，查看嵌套列表中所有元素的索引:

(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
(3,0) (3,1) (3,2) (3,3) (3,4)
(4,0) (4,1) (4,2) (4,3) (4,4)

从这里你可以写下对角线上半部分的索引，以获得模式的感觉:

(0,4)
(0,3), (1,4)
(0,2), (1,3), (2,4)
(0,1), (1,2), (2,3), (3,4)
(0,0), (1,1), (2,2), (3,3), (4,4)

我们如何生成这些配对列表?首先，让我们看看外部循环。外部循环将遍历第一个子列表的顶部，即对(0,j)，其中j从最后一个索引开始计数:

for j in range(len(puzzle), -1, -1):
    print((0, j))
#output:
(0, 4)
(0, 3)
(0, 2)
(0, 1)
(0, 0)

然后我们需要让我们的内部循环在每一步都向下并向右移动，并且永远不会超过列表的末尾:

for j in range(len(puzzle), -1, -1):
    for i in range(len(puzzle)):
        j += 1
        if j > len(puzzle):
             break
        print((i,j))
    print("")

输出:

(0, 4)
(0, 3)
(1, 4)
(0, 2)
(1, 3)
(2, 4)
(0, 1)
(1, 2)
(2, 3)
(3, 4)

如果你让外环从N..-1出发，那么你也可以得到穿过中心的对角线。之后，使用类似的逻辑获得对角线的下半部分。

要使对角线在另一个方向上运行，您可以再次使用相同的逻辑(通过查看您想要的索引，编写外部循环，然后编写内部循环)，或者您可以只是反转每个子列表(将其视为查看镜像，或在垂直线上反射2d数组!当你这样做的时候，所有的对角线将以"相反"的方向穿过元素)。

Answer 2

这样想:

1. 行中发现的单词为序列puzzle[a][b+i]

2. 列中发现的单词为序列puzzle[a+i][b]

3. 对角线上的词是puzzle[a+i][b+i]或puzzle[a+i][b-i]序列

对于i=0,...,n，每个对于一些整数a,b,n，这样产生的所有索引都在表中。您可以向前或向后检查序列。附加的约束，比如只考虑完整的行，可以通过在a,b,n上放置约束来实现。特别地，我解释它的方式是你想要在每种情况下最长的字符串;在本例中，您只需将n设置为每个a,b的最大可能值。

你已经有1个了。和2。下来。我建议您从列的解决方案开始，并尝试将其应用于3中描述的序列。div。