在二维数组中查找字符串

Question

这是一个需要针对时间进行优化的面试问题.

假设您有一个二维数组,并且您在数组中有一个字符串说"亚马逊",这样各个字符可以从左到右,从右到左,从上到下,从下到上.

我将用例子解释:

char[][] a = {
            {B,B,A,B,B,N},
            {B,B,M,B,B,O},
            {B,B,A,B,B,Z},
            {N,O,Z,B,B,A},
            {B,B,B,B,B,M},
            {B,B,B,B,B,A}
    };

上面的Array有两个Amazon Strings.您需要返回存在的此类字符串的数量.

Answer 1

您可以从矩阵中具有“A”的每个单元运行 BFS，并计算可以构建 Amazon 的方式数量。最后将它们全部添加。

边：如果相邻（上、下、左、右）节点（单元格）包含 Amazon 的下一个字符，则该节点（单元格）具有从当前节点（单元格）开始的有向边。仅作为示例，具有“N”的所有相邻节点都具有来自具有“O”的节点的有向边。