通过确定在矩阵中找到单词字符串的次数来进行字符串搜索

Question

我们得到一个字符矩阵和一组不同的单词。我希望确定给定单词在矩阵中出现的总次数，并遵守以下有关矩阵内导航的规则：

• 当可以通过沿着矩阵中的某些路径组合字符来形成单词时，就找到了该单词；
• 路径可以从任何单元格开始，并且最初必须到达右侧的单元格或下面的单元格；
• 搜索从左上角的单元格开始；和
• 所有路径都可以改变方向一次，朝相反的方向前进（到左边的单元格或上面的单元格）。

例如，假设矩阵是

[["a", "b", "a", "c"],
 ["x", "a", "c", "d"],
 ["y", "r", "d", "s"]]

单词列表是

["ac", "cat", "car", "bar", "acdc", "abacaba", "xab", "dra"]

发现这些单词在矩阵中拖欠如下。

• "ac"

  可以通过 3 种方式形成（

  matrix[0][2]->matrix[0][3]

  、

  matrix[0][2]->matrix[1][2]

  和

  matrix[1][1]->matrix[1][2]

  ；
• 字符串

  "cat"

  和

  "car"

  无法组成，因此不影响计数；

• "bar"

  可以通过 1 种方式形成 (

  matrix[0][1]->matrix[1][1]-> matrix[2][1]

  );

• "acdc"

  可以通过 2 种方式形成（

  matrix[0][2]->matrix[1][2]->matrix[2][2]->matrix[1][2]

  和

  matrix[1][1]->matrix[1][2]->matrix[1][3]->matrix[1][2]

  ）；和

• "abacaba"

  可以通过 1 种方式形成

  (matrix[0][0]->matrix[0][1]->matrix[0][2]->matrix[0][3]->matrix[0][2]->matrix[0][1]->matrix[0][0]

  );

• "xab"

  可以通过 1 种方式形成 (

  matrix[1][0]->matrix[1][1]-> matrix[0][1]

  )；和

• "dra"

  可以通过 1 种方式形成 (

  matrix[2][2]->matrix[2][1]-> matrix[1][1]

  )。

请注意，

"xab"

和

"dra"

各有一个方向变化。

因此发现总计数等于

3+1+2+1+1+1 = 9

。

Answer 1

你一开始说我们可以向右走，也可以向下走。但对于“dra”这个词，你最初要向左走，而你应该向右或向下走。