在一个二维数组中查找字符串

Question

在一个二维数组中查找字符串

8

这是一个需要优化时间的面试问题。

假设您有一个二维数组，并且在该数组中有一个字符串，比如“Amazon”，该字符串的各个字符可以从左到右，从右到左，从上到下和从下到上出现。

我来举个例子：

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}
    };

以上数组有两个Amazon字符串。您需要返回此类字符串的数量计数。

- Geek

寻找第一个字符并按照方向查找后续字符。 - Elanchezhian Narayanasamy

在字符串中可以使用相同的位置两次吗？例如，MAZON算作一个出现吗？（从A开始向左和向右移动） - Henry

2

如果第四个数组是{N,O,Z,O,N,A}，算法会返回3还是2？ - AnotherGeek

@AnotherGeek：我想你的意思是NOZOMA，而不是3。 - Geek

从你的问题中并不清楚字符串是否只能单向移动，或者可以使用环绕。 - SpaceTrucker

我从来没有考虑过环绕，他们也没有告诉我。我建议先尝试非环绕的方法。 - Geek

6个回答

1

你可以从矩阵中每个包含'A'的单元格开始运行BFS，并计算亚马逊公司可以建立的方式数量。最后将它们全部加起来。

边缘：如果相邻（上下左右）节点（单元格）包含亚马逊公司的下一个字符，则从当前节点（单元格）向该节点添加有向边缘。例如，所有具有“N”的相邻节点都从具有“O”的节点拥有有向边缘。

- MMHossain

1

你只给了一个例子。如果：

所有的“填充”字符都不在字符串中
字符串始终完整且未分割
字符串至少有一个非重复字母

那么你只需要计算有多少个这些非重复字母。例如，对于“AMAZON”，你只需要计算数组中有多少个“Z”（或“M”、“O”或“N”）。

这并不像路径查找算法那样通用，但肯定更快。

- ChatterOne

填充字符可以是任何东西。字符串可以是任何东西。 - Geek

1

遍历矩阵 = O(N^2)
在Amazon中找到key[0]即'A'的第一次出现，并将其存储在[i,j]中
从matrix[i,j]开始，尝试使用所有四个方向来追踪'Amazon'

a. 您可以使用BFS或DFS

b. 如果找到，则将计数增加1

c. 如果未找到，请继续

时间复杂度为O(N^2 + N) {使用DFS}

- Vikram Singh

1

创建一个三维表格，其中矩阵中的每个位置都指向一个表示字母表中每个字母的数组。从左到右和从右到左，逐行执行两次迭代：如果字符串存在，则会遇到其第一个或最后一个字母（如果已经看到了其连接匹配的第一部分或最后一部分，则可能会遇到中间字母）。汇总左右查找结果，但将下面元素的位置制表在表示当前长度和方向的下一个可能字符的索引处。如果遇到表格匹配，则将其转换为完整匹配或另一个部分匹配（每个这样的字母+位置单元格可以容纳多个潜在匹配）。

- גלעד ברקן

0

我已经编写了一个Java代码来解决这个问题

但是从时间复杂度的角度来看，这是一种昂贵的解决方案

因为我要遍历2D数组以查找'A'，然后从该元素开始向4个方向遍历以查找'M'、'A'等等

所以最坏的情况是，如果我们假设对数组进行1次扫描的时间复杂度为n^2，扫描的单词长度为K

那么时间复杂度将会是

O(N^2 * K^4)，其中的4代表我们必须搜索的4个方向

以下是完整运行的类：

public class Treetest {


public static void main(String[] args) {
    char[][] a = {
            {'B', 'B', 'A', 'B', 'B', 'N'},
            {'B', 'B', 'M', 'B', 'B', 'O'},
            {'B', 'B', 'A', 'B', 'B', 'Z'},
            {'N', 'O', 'Z', 'A', 'M', 'A'},
            //{'N', 'O', 'Z', 'B', 'B', 'A'},
            {'B', 'B', 'B', 'B', 'B', 'M'},
            {'B', 'B', 'B', 'B', 'B', 'A'}
    };

    int vertical = 0;
    int horiz = 0;
    int solutioncount = 0;
    for (char[] horizantal : a) {

        for (char element : horizantal) {
            if (element == 'A') {
                if (findnextChar(horiz, vertical, "A", a))
                    solutioncount++;
            }
            horiz++;
        }
        horiz = 0;
        vertical++;
    }
    System.out.println("Solution Count is : " + solutioncount);
}

public static boolean findnextChar(int posx, int posy, String currentFind, char[][] a) {
    char nextchar = 0;
    boolean checkMatch = false;
    switch (currentFind) {
        case "A":
            nextchar = 'M';
            break;
        case "AM":
            nextchar = 'A';
            break;
        case "AMA":
            nextchar = 'Z';
            break;
        case "AMAZ":
            nextchar = 'O';
            break;
        case "AMAZO":
            nextchar = 'N';
            checkMatch = true;
            break;

    }
    String nextString = currentFind + String.valueOf(nextchar);
    if (posx - 1 >= 0 && a[posy][posx - 1] == nextchar) {
        if (checkMatch) {
            return true;
        }
        return findnextChar(posx - 1, posy, nextString, a);
    }
    if (posx + 1 <= a[0].length - 1 && a[posy][posx + 1] == nextchar) {
        if (checkMatch) {
            return true;
        }
        return findnextChar(posx + 1, posy, nextString, a);

    }
    if (posy - 1 >= 0 && a[posy - 1][posx] == nextchar) {
        if (checkMatch) {
            return true;
        }
        return findnextChar(posx, posy - 1, nextString, a);

    }
    if (posy + 1 <= a[0].length - 1 && a[posy + 1][posx] == nextchar) {
        if (checkMatch) {
            return true;
        }
        return findnextChar(posx, posy + 1, nextString, a);
    }
    return false;

}

}

- Hani

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- poorvank · Accepted Answer

我已经实现了一个简单的广度优先搜索算法（bfs），每次搜索时，将要查找的字符串 toFind（在这种情况下是 AMAZON）的第一个字符与二维数组中的字符进行匹配。使用了一个简单的 visited 二维数组，在一次迭代中检查标记的字符：

public class FindStrings {

private static int count = 0;       // Final Count

public static void find(Character[][] a, String toFind) {

    int rows = a.length;
    int col = a[0].length;

    boolean[][] visited = new boolean[a.length][a[0].length];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < col; j++) {
            if (a[i][j] == toFind.charAt(0)) {
                findUtil(visited, a, i, j, 0, toFind, new StringBuilder(), rows - 1, col - 1,new ArrayList<String>());
                visited[i][j] = false;
            }
        }
    }

}

private static void findUtil(boolean[][] visited, Character[][] a, int i, int j, int index, String toFind, StringBuilder result, int R, int C,ArrayList<String> list) {

    result.append(a[i][j]);
    //This list just prints the entire Path
    list.add(i+"-"+j);
    if (index == toFind.length() - 1 && result.toString().equals(toFind)) {
        System.out.println(list.toString());
        count++;
        return;
    }
    visited[i][j] = true; // Just to mark the character so that one character is not visited twice for a string match
    int nextIndex = index + 1; //Next index of the String to be compared

    int nextR, nextC;

    //Down
    if (i + 1 >= 0 && j >= 0 && i + 1 <= R && j <= C && !visited[i + 1][j] && a[i + 1][j] == toFind.charAt(nextIndex)) {
        nextR = i + 1;
        nextC = j;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        //Every time we are done with the next character in the 2D Array we mark it visited
        visited[nextR][nextC] = false;
    }
    //Right
    if (i >= 0 && j + 1 >= 0 && i <= R && j + 1 <= C && !visited[i][j + 1] && a[i][j + 1] == toFind.charAt(nextIndex)) {
        nextR = i;
        nextC = j + 1;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }
    //Left
    if (i >= 0 && j - 1 >= 0 && i <= R && j - 1 <= C && !visited[i][j - 1] && a[i][j - 1] == toFind.charAt(nextIndex)) {
        nextR = i;
        nextC = j - 1;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }
    //Up
    if (i - 1 >= 0 && j >= 0 && i - 1 <= R && j <= C && !visited[i - 1][j] && a[i - 1][j] == toFind.charAt(nextIndex)) {
        nextR = i - 1;
        nextC = j;
        findUtil(visited, a, nextR, nextC, nextIndex, toFind, new StringBuilder(result), R, C,new ArrayList<>(list));
        visited[nextR][nextC] = false;
    }


}

public static int getCount() {
    return count;
}

public static void main(String[] args) {

    Character[][] a = new Character[][]{
            {'B', 'B', 'A', 'B', 'B', 'N'},
            {'B', 'B', 'M', 'B', 'B', 'O'},
            {'B', 'B', 'A', 'B', 'B', 'Z'},
            {'B', 'O', 'Z', 'O', 'N', 'A'},
            {'B', 'B', 'O', 'Z', 'B', 'M'},
            {'B', 'B', 'N', 'A', 'M', 'A'}
    };

    String toFind = "AMAZON";

    find(a, toFind);
    System.out.println(getCount());

}