algorithm - 列出拼图中所有单词的最快算法

Question

我在一次面试中被问到这个问题，我很好奇最佳答案。问题是这样的:给你一个 n x n 的棋盘，上面写满了字母。一个游戏算法想要找到并列出棋盘上所有可能的单词，其中“一个单词”被定义为至少由 3 个字母组成的字符串，可以是水平的，也可以是垂直的。执行此操作最省时的方法是什么？

这个问题中的“单词”不需要是字典中的真实单词。关键是尽可能快地找到所有可接受长度的字符串。我想不出别的，只能用蛮力的方式遍历棋盘上的所有空间，找到该空间中所有以字母开头的字符串，需要O(n^3)的时间。你们会怎么做？

附言。我看到这个问题被否决了，因为人们认为没有更好的解决方案。然而，这是一个微软面试问题，我的面试官明确告诉我我的答案不是最优的。

Answer 1

这是我分阶段解决问题的方法:

1. 尝试在拼图中找到一个给定的单词:您可以使用 DFS 在拼图中找到一个单词。这将是 O(n^2)，因为我们必须遍历每一行和每一列字符。

2. 在一个谜题中找到所有给定的单词:如果给定了 x 个单词，您可以对每个单词使用上述算法。复杂度为 O(x*n^2)。

3. 如果有相同前缀的单词，那么我们将重复搜索前缀的工作。这可以通过为给定的单词构建 T​​rie 结构并将 trie 的 DFS 与拼图的 DFS 相结合来避免。

这是第一步在 C++ 中的粗略实现:

bool FindWordInPuzzle(int i, int j, char nextChar, int nextCharId, string word, int m, int n, bool **mark, char **maze)
{
    int move[8][2] = { 0, -1, -1, -1, -1, 0, -1, 1, 0, 1, 1, 1, 1, 0, 1, -1 };
    mark[i][j] = 1;

    for (int r = 0; r < 8; r++) {
        int g = i + move[r][0];
        int h = j + move[r][1];

        if (g > 0 && g < m + 2 && h > 0 && h < m + 2 && mark[g][h] == 0 && maze[g][h] == nextChar) {
            nextCharId++;

            if (nextCharId >= word.length()) {
                return true;
            }

            if (FindWordInPuzzle(g, h, word[nextCharId], nextCharId, word, m, n, mark, maze)) {
                return true;
            }
        }
    }

    return false;
}

bool FindWord(char **maze, bool **mark, int m, int n, string word) {
    char currentChar = word[0];
    int currentCharId = 0;
    for (int row = 1; row < m + 2; row++) {
        for (int col = 1; col < n+2; col++) {
            if (maze[row][col] == currentChar && mark[row][col] == 0) {
                currentCharId++;
                if (currentCharId >= word.length()) {
                    return true;
                }

                if (FindWordInPuzzle(row, col, word[currentCharId], currentCharId, word, m, n, mark, maze)) {
                    return true;
                }
            }

            currentCharId = 0;
            currentChar = word[0];
        }
    }

    return false;
}

int main() {
    string word;
    int m, n;

    cin >> word;
    if (word.length() <= 0) return 0;

    cin >> m >> n;
    char** maze;
    bool **mark;

    // declare arrays
    maze = new char*[m + 2];
    mark = new bool*[m + 2];
    for (int i = 0; i < m + 2; i++) {
        maze[i] = new char[n + 2];
        mark[i] = new bool[n + 2];
    }

    // boundaries
    for (int i = 0; i < m + 2; i++) {
        maze[0][i] = ' ';
            maze[i][0] = ' ';
        maze[0][m + 1] = ' ';
        maze[i][m + 1] = ' ';

        mark[0][i] = 1;
        mark[i][0] = 1;
        mark[0][m + 1] = 1;
            mark[i][m + 1] = 1;

    }

    // get values
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            cin >> maze[i][j];
            mark[i][j] = 0;
        }
    }

    bool val =  FindWord(maze, mark, m, n, word);
    cout << val;
    cin >> word;

    return 0;
}