algorithm - 就时间复杂度而言，使用最佳方法从字符矩阵形成字符串的方法有多少？

Question

(更新)

我们需要找到从字符矩阵中可以形成给定字符串的方式数 .

我们可以从矩阵中的任何位置 (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)

Sample test cases:

(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(字符串的长度)长度路径以形成字符串。

How can we improve the solution efficiency?

Answer 1

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

如果单元格中的字符出现在输入字符串的任何位置，我们只关心矩阵的单元格。因此，如果我们的输入字符串是 'fit'，我们就不会关心包含字母 'z' 的单元格。

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

取输入字符串，首先将它的字符放入集合S中。这是一个O(k)的步骤，其中k是字符串的长度；

接下来我们迭代矩阵(一个 O(m*n) 步骤)并且:

如果单元格中的字符没有出现在S中，我们继续下一个；

如果单元格中的字符出现，我们在名为 M 的 > 映射中添加单元格位置的条目。

现在，迭代输入(不是矩阵)，对于当前字符 c 出现的每个位置，获取当前单元格的右侧、左侧、上方和下方的未访问位置；

如果这些位置中的任何一个出现在 M 中下一个字符出现在矩阵中的单元格列表中，则:

递归地转到输入字符串的下一个字符，直到用完所有字符。

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

建议 - 2:动态规划

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

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