4

（更新）

我们需要找出可以从字符矩阵中形成给定字符串的方法的数量。

我们可以从矩阵中的任何位置(i, j) 开始形成单词，并且可以从矩阵的每个单元格(i, j) 可用的 8 个方向中的任何未访问方向前进，即

(i + 1, j)
(i + 1, j + 1)
(i + 1, j - 1)
(i - 1, j)
(i - 1, j + 1)
(i - 1, j - 1)
(i, j + 1)
(i, j - 1)

示例测试用例：

(1) input:

N = 3 (length of string) 
string = "fit"
matrix:   fitptoke   
          orliguek   
          ifefunef 
          tforitis

output: 7

(2) input:

N = 5 (length of string) 
string = "pifit"
matrix:   qiq
          tpf
          pip
          rpr

output: 5

解释：

使“适合”的方法数量如下所示：

(0,0)(0,1)(0,2)
(2,1)(2,0)(3,0)
(2,3)(1,3)(0,4)
(3,1)(2,0)(3,0)
(2,3)(3,4)(3,5)
(2,7)(3,6)(3,5) 
(2,3)(1,3)(0,2)

我以一种天真的方式接近解决方案，转到矩阵中的每个可能位置 (i,j)，并通过对矩阵执行 DFS 搜索从该单元格 (i,j) 开始形成字符串，并添加形成方法的数量从 pos (i, j) 到 total_num_ways 变量的给定字符串。

伪代码：

W = 0
for i : 0 - n:
   for j: 0 - m:
        visited[n][m] = {false}
        W += DFS(i, j, 0, str, matrix, visited);

但事实证明，这个解决方案的时间复杂度是指数级的，因为我们要去每一个可能的 n * m 位置，然后遍历每一个可能的 k（字符串长度）长度路径来形成字符串。

我们如何提高解决方案的效率？

4

2 回答 2

0

建议 - 1：预处理矩阵和输入字符串

如果单元格中的字符出现在输入字符串的任何位置，我们只关心矩阵的单元格。所以，如果我们的输入字符串是“fit”，我们不关心包含字母“z”的单元格。

使用它，以下是一个建议。

  1. 取输入字符串，首先将其字符放入集合S中。这是一个 O(k) 步，其中k是字符串的长度；
  2. 接下来我们迭代矩阵（一个 O(m*n) 步骤）并且：
    1. 如果单元格中的字符没有出现在S中，我们继续下一个；
    2. 如果单元格中的字符出现，我们在名为M的 > 映射中添加单元格位置条目。
  3. 现在，遍历输入（不是矩阵），对于当前字符c出现的每个位置，获取当前单元格的右侧、左侧、上方和下方的未访问位置；
  4. 如果这些位置中的任何一个出现在M中的单元格列表中，其中下一个字符出现在矩阵中，则：
    1. 递归地转到输入字符串的下一个字符，直到用完所有字符。

这个解决方案有什么更好的？我们在 O(1) 中得到了我们需要探索的下一个单元，因为它已经存在于地图中。结果，复杂度不再是指数级的，而是实际上是 O(c)，其中c是矩阵中输入字符串的总出现次数。

建议 - 2：动态规划

在存在最优子结构和重叠子问题的情况下，DP 会有所帮助。因此，在相同子字符串是多个解决方案的一部分的情况下，使用 DP 可能会有所帮助。

例如：如果我们在某处找到“fit”，那么如果相邻单元格中有一个“f”，它可以使用我们找到的第一个“fit”中的子字符串“it”。这样一来，当我们遇到之前探索过的子字符串时，我们就可以防止递归字符串的其余部分。

于 2020-03-30T04:25:06.623 回答
-1 
# Checking if the given (x,y) coordinates are within the boundaries
# of the matrix
def in_bounds(x, y, rows, cols):
    return x >= 0 and x < rows and y >= 0 and y < cols

# Finding all possible moves from the current (x,y) position
def possible_moves(position, path_set, rows, cols):
    moves = []
    move_range = [-1,0,1]
    for i in range(len(move_range)):
        for j in range(len(move_range)):
            x = position[0] + move_range[i]
            y = position[1] + move_range[j]
            if in_bounds(x,y,rows,cols):
                if x in path_set:
                    if y in path_set[x]:
                        continue
                moves.append((x,y))
    return moves

# Deterimine which of the possible moves lead to the next letter 
# of the goal string
def check_moves(goal_letter, candidates, search_space):
    moves = []
    for x, y in candidates:
        if search_space[x][y] == goal_letter:
            moves.append((x,y))
    return moves

# Recursively expanding the paths of each starting coordinate
def search(goal, path, search_space, path_set, rows, cols):
    # Base Case
    if goal == '':
        return [path]
    x = path[-1][0]
    y = path[-1][1]
    if x in path_set:
        path_set[x].add(y)
    else:
        path_set.update([(x,set([y]))])

    results = []
    moves = possible_moves(path[-1],path_set,rows,cols)
    moves = check_moves(goal[0],moves,search_space)

    for move in moves:
        result = search(goal[1:], path + [move], search_space, path_set, rows, cols)
        if result is not None:
            results += result
    return results

# Finding the coordinates in the matrix where the first letter from the goal
# string appears which is where all potential paths will begin from.
def find_paths(goal, search_space):
    results = []
    rows, cols = len(search_space), len(search_space[0])
    # Finding starting coordinates for candidate paths
    for i in range(len(search_space)):
        for j in range(len(search_space[i])):
            if search_space[i][j] == goal[0]:
                # Expanding path from root letter
                results += search(goal[1:],[(i,j)],search_space,dict(),rows,cols)
    return results

goal = "fit"
matrix = [
        'fitptoke',
        'orliguek',
        'ifefunef',
        'tforitis'
        ]

paths = find_paths(goal, matrix)
for path in paths:
    print(path)
print('# of paths:',len(paths))

不是从矩阵的每个坐标扩展路径，而是首先迭代矩阵以找到与目标字符串的第一个字母具有相同字母的所有 (i,j) 坐标。这需要 O(n^2) 时间。

然后，对于找到的每个 (i,j) 坐标，其中包含目标字符串中的第一个字母，通过从目标字符串中搜索第二个字母来扩展路径，并仅扩展与第二个字母匹配的路径。对目标字符串中的每个字母重复此操作，以递归地查找从起始坐标开始的所有有效路径。

于 2020-03-25T04:51:10.653 回答