用复数遍历二维数组中的邻域

2021-09-27 05:10:09 发布

您现在位置:Python中文网/ 问答频道 /正文

在这个解中,我发现了一种用复数遍历四重子邻域的新方法。你知道吗

https://leetcode.com/problems/word-search-ii/discuss/59804/27-lines-uses-complex-numbers

(你可以看看我的例子。)

我认为这是优雅和简洁,但我不能完全理解它。你知道吗

这里我提取了关键代码,并简化了exmaple。你知道吗

board是一个2d数组,我们要从每个节点开始,通过dfs递归地遍历4个方向的neigbor:

这是一种常见的方法:

    def dfs(i, j, word):
        # create 4 direction by hand
        for I, J in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
            # need to check boundary
            if 0 <= I < len(board) and 0 <= J < len(board[0]):
                dfs(I, J, word + c)

    for i, j in board:
        dfs(i, j, '')

这里使用复数作为索引:

    board = {i + 1j * j: c
             for i, row in enumerate(board)
             for j, c in enumerate(row)}

    def dfs(z, word):
        c = board.get(z)

        # here is visit 4 direction neighbors, which I don't understand
        if c:
            for k in range(4):
                search(node[c], z + 1j ** k, word + c)

    for z in board:
        dfs(z, '')

我认为使用复数有两个好处:

  1. 不需要手动创建4个方向
  2. 不需要检查边界

但我不能理解这里for k in range(4): dfs(z + 1j ** k, word + c)

有人能解释一下这个算法吗?真的很感激。你知道吗