2

我在一次采访中被问到这个问题，我很好奇最佳答案。问题是这样的：给你一个充满字母的 nxn 板。一个游戏算法想要在这个板上找到并列出所有可能的单词，其中“一个单词”被定义为水平或垂直至少 3 个字母的字符串。什么是最省时的方法？

这个问题中的“单词”不需要是字典中的真实单词。关键是尽可能快地找到所有可接受长度的字符串。除了遍历板上所有空间并找到以该空间中的字母开头的所有字符串外，我想不出其他任何方法，这需要 O(n^3) 时间。你们会怎么做？

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

4

4 回答 4

2

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

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

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

  3. 如果存在具有相同前缀的单词，那么我们将重复为搜索前缀所做的工作。这可以通过为给定的单词构建一个 Trie 结构并将 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;
}
于 2015-07-18T16:43:16.707 回答
1

让m(x) = max {0, x}. 如果我们使用从 0 开始的索引，则有

s(x,y) = m(x-1) + m(n-x-2) + m(y-1) + m(n-y-2)

从 position 开始的单词(x,y)。水平方向，左侧以 column 结尾，0, 1, ..., y-2右侧以 column 结尾x+2, x+3, ..., n-1。垂直词也类似。

因此，在每个位置，都从2*(n-3)和2*(n-2)单词开始（包括）。

更准确地说，在位置，当且仅当或时，(x,y)开始水平词，否则词。这使得每行水平单词。每列的垂直字数是一样的，所以一共有n-2y = 0y = n-1n-32*(n-2) + (n-2)*(n-3) = (n-1)*(n-2)

2*n*(n-1)*(n-2)

不一定是网格中不同的单词。假设一个不太小的字母表，重复的比例平均不会很大，所以不可能有一个复杂度低于 的算法O(n³)。

如果不考虑重复，就是这样，并且只剩下遍历数组的低级变化。

如果要删除重复项，并且目标是尽可能有效地列出所有不同的单词，那么问题是哪种数据结构允许尽可能有效地删除重复项。我无法回答这个问题，但我认为 trie 会非常有效。

于 2012-10-13T19:14:32.783 回答
0

这里有两个问题-一个：天真的解决方案蛮力不是O(n^3)，而是O(n^4)。

假设您将每个子字符串复制到列表中的新条目。你有O(n^3)话。但是，这些中的每一个都是O(n)（平均而言）本身，因此将所有这些子字符串复制到列表实际上是O(n^4).

二：
更有效的解决方案是维护一个trie数据结构，并使用 DFS 来填充它，就像从矩阵中的每个索引（向右和向下）遍历。

这将导致用单词O(n^3)填充 trie 的解决方案。O(n^3)

于 2012-10-13T19:17:11.430 回答
0

你为什么说O(n^3)？棋盘是正方形的，正方形是O(n^2)。

代码如下：

for(int col=0; col<n-2; ++col) {
    for(int row=0; row<n-2; ++row) {
        // for given (row,col)
        // yield word to right
        // yield word down
        // yield word down-right
    }
}

这是O(3*n^2).

如果您也想反转，那么它将是O(6*n^2)

C# 中的真实代码

class Program
{
    private static Random rnd = new Random();

    static void Main(string[] args)
    {

        string alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        char[,] letters = new char[5, 5];
        int counter = 0;

        // filling and printing
        for (int i = 0; i < letters.GetLength(0); ++i)
        {
            for (int j = 0; j < letters.GetLength(1); ++j)
            {
                letters[i, j] = alphabet[rnd.Next(alphabet.Length)];
                Console.Write(letters[i,j]);
            }
            Console.WriteLine("");
        }



        // generating "words"

        for (int i = 0; i < letters.GetLength(0)-2; ++i)
        {
            for (int j = 0; j < letters.GetLength(1)-2; ++j)
            {
                // horizontally
                Console.Write(counter.ToString() + ": ");

                Console.Write(letters[i, j]);
                Console.Write(letters[i, j+1]);
                Console.Write(letters[i, j+2]);

                Console.WriteLine("");
                counter++;

                // vertically
                Console.Write(counter.ToString() + ": ");

                Console.Write(letters[i, j]);
                Console.Write(letters[i+1, j]);
                Console.Write(letters[i+2, j]);

                Console.WriteLine("");
                counter++;

                // diagonally
                Console.Write(counter.ToString() + ": ");

                Console.Write(letters[i , j]);
                Console.Write(letters[i + 1, j+1]);
                Console.Write(letters[i + 2, j+2]);

                Console.WriteLine("");
                counter++;
            }
        }



    }
 }

输出

长波微波
OWWGR
APVOM
GKECL
TXCPD
0：LWI
1：协议书
2：低电压值
3：WID
4：WWP
5：世界大战
6：IDM
7: IWV
8：IGM
9：OW
10：奥格
11：欧佩克
12：世界工作组
13：WPK
14：WVC
15：WGR
16：WVE
17：WOL
18：APV
19：AGT
20：AKC
21: PVO
22: PKX
23：PEP
24: 声音
25：VEC
26：VCD

结果数为 27 = 3*(5-2)^2

于 2012-10-13T19:20:52.567 回答