社区首页 >问答首页 >查找是否可以从字符矩阵中获取字符串。

问查找是否可以从字符矩阵中获取字符串。
EN

Stack Overflow用户

提问于 2014-06-02 18:34:05

回答 3查看 2.1K关注 0票数 3

给定一个字符矩阵和一个字符串，查找是否可以从该矩阵中获得该字符串。从矩阵中的每个字符，我们可以向上/向下/右/左移动。例如，如果matrix3是：

o f a s
l l q w
z o w k

字符串是follow，那么函数应该返回true。

我能想到的唯一方法是一个回溯算法，它可以搜索单词是否可能。还有其他更快的算法来解决这个问题吗？

假设我有很多疑问(关于找出一个单词是否存在)。那么，是否可以进行一些预处理，以更快地回答查询？

algorithm

matrix

language-agnostic

backtracking

回答 3

Stack Overflow用户

回答已采纳

发布于 2014-06-02 22:06:23

您可以使用DFS解决这个问题。让我们为这个问题定义一个图。图的顶点将包括矩阵的一个单元格组合的单元格和我们正在搜索的字符串的前缀长度。当我们处于给定的顶点时，这将意味着到目前为止，指定前缀的所有字符都匹配，并且我们目前处于给定的单元格中。

我们将边定义为相邻的连接单元并执行“有效”事务。这就是我们要搜索的字符串中的下一个单元格。

为了解决这个问题，我们从包含字符串的第一个字母和前缀长度1的所有单元格中执行DFS (这意味着我们已经匹配了这个第一个字母)。从那里开始，我们继续搜索，在每个步骤上，我们计算出从当前位置出去的边(单元格/字符串前缀长度组合)。我们第一次到达长度为L的前缀时终止--字符串的长度。

请注意，DFS可能被认为是回溯，但更重要的是跟踪我们已经访问过的图中的节点。因此，总体复杂性受N * M * L约束，其中N和M是矩阵的维数，L是字符串的长度。

票数 2

Stack Overflow用户

发布于 2014-06-04 01:23:00

当然，您可以找到所有可能的字符串(从字符开始，并尽可能深入)。这可以通过递归函数来完成。

网格：

abc
def
ghi

字符串：

abcfedghi
abcfehgd
abcfehi
abedghif
abefc
abefighd
abehgd
abehifc
ad...
...

然后对这些字符串进行排序，在查找单词时，在列表上使用二进制搜索。(在查找n个字母单词时，当然只考虑列表中字符串的前n个字母。)大量的准备和大量的内存需要，但搜索将很快。因此，如果您一次又一次地使用相同的网格，准备工作最终可能会支付:-)

票数 1

Stack Overflow用户

发布于 2016-01-19 23:48:17

下面是用于查找给定字符串是否存在于给定矩阵中的伪代码。这里访问了跟踪字符串在矩阵中的位置，它使用回溯来跟踪这个字符串。我希望这是有帮助的。

bool isSafe(matrix[n][m], int visited[n][m], int i, int j, int n, int m){

if(i<m && j<n && i>=0 && j>=0 && visited[i][j] == 0)
    return true;
return false;
}

bool dfs(char matrix[n][m], int i, int j, int visited[n][m], char str[], int index){

if(index == strlen(str))
    return true;

// row moves
int x[] = {-1, 0, 1, -1};
// col moves
int y[] = {0, -1, 1, 0};

if(str[index] == matrix[i][j]){
    visited[i][j] = 1;
    // for all the neighbours
    for(int k = 0; k<4; k++){
        // mark given position visited
        next_x = i + x[k];
        next_y = j + y[k];

        if(isSafe(matrix, visited, next_x, next_y, n, m)){
            if(dfs(matrix, next_x, next_y, visited, str, index+1) == true)
                return true;
        }
    }
    // backtrack
    visited[i][j] = 0;

}

return false;

}

bool isPresent(char matrix[n][m], char str[]){

// visited initialized to 0
int visited[n][m] = {0};

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++){
        if(dfs(matrix, i, j, n, m ,visited, str, 0) == true)
            return true;
    }


return false;
}