7

最近偶然发现这个面试问题，

给定一个二维字符数组和一个可以及时搜索单词的字典O(1)。需要打印字典中存在的数组中的所有单词。单词可以在任何方向形成，但必须在数组的任何边缘结束。（不必太担心字典）

输入： 

a f h u n
e t a i r
a e g g o
t r m l p

输出：

after
hate
hair
air
eat
tea

注意：这里的“egg”不是字典词，因为它没有在数组的边缘结束。

我以前见过类似的问题，但从来没有想到一个好的算法来解决这类问题。关于如何解决这类问题（从字符数组形成单词）的任何帮助都将非常有帮助。

（我能想到的唯一方法是在二维数组中找到所有可能的字符排列，并检查它是否在数组的边缘结束，并检查排列是否是 O(1) 中字典中的有效单词时间）

4

4 回答 4

3

将数组转换为图形，以便每个单元格[i,j] 都具有与其 4 个邻居中的每一个共享的边[i+1,j], [i-1,j], [i,j+1], [i,j-1]。然后在每个 array-edge-cell 上运行 DFS 并继续检查字典中是否有反向的单词。

于 2012-12-03T09:57:53.283 回答
2

你没有提到一个字符只能使用一次 - 所以没有这个限制是“我们可以生成 k（或更多）不同的单词吗？”的问题。是不可判定的。1 .

（由于每个元素的“访问”数量受到限制，存在有限数量的可能性，并且主张和证明当然不成立）。

证明：
众所周知，没有算法A可以决定终止算法是否返回B或更多不同的输入。（如果需要，稍后将查找此声明的引用，现在相信我）。truek

我们将展示给定一个算法A，如果有k或更多生成的单词 - 我们可以决定是否有k或更多不同的输入产生“真”：

  1. 让决定是否有k或更多生成词的（终止）算法为M。

  2. 不失一般性 - 假设二进制字母（我们可以用它来表示一切）。

  3. 让：

     array = 0 1 
         0 1

    请注意，我们可以在此数组上行走时生成任何二进制字。

算法 A：
输入：算法 B，自然数 n
输出：当且仅当算法 B 对 n 个或更多不同的输入回答“真”时为真。
算法：
(1)B(word)用作黑盒字典 - 如果答案为真，则word在字典中。
(2)array用作数组。
(3) 在 (array,dictionary,n) 上运行 M，并像它一样回答。

请注意，如果 M 回答为真 -> 有n或更多接受的词 -> B 有n或更多不同的输入产生真（字典的定义，因为我们可以用数组生成每个输入） -> 问题的答案是真的.
（如果算法回答错误，则证明是相似的）。

量子点

结论：
如果我们可以重复数组中的一个字符而不是一次（或者准确地说 - 无限次） - 那么如果没有字典上的任何信息，问题就无法解决。

(1) 不可判定问题是没有算法可以在 100% 的情况下正确回答 TRUE/FALSE 的问题 - 对于每种算法，在某些情况下算法会“卡”在无限循环中（或给出错误的答案）。最常见的“不可判定”问题是停止问题——它说——没有算法A可以采用任何算法并在停止某些输入B时回答。Bw

于 2012-12-03T10:58:57.600 回答
0

我的解决方案是：

我想我有一个 M*N 数组，并且搜索单词没有限制。例如，“rood”和“door”是两个不同的词，因为它们是相互颠倒的。

从第一个字母开始（左，上）。在这种情况下，它是“a”。并检查字典中是否有单词（假设有以'ae'和'af'开头的单词）检查它们是否已经是单词并且最后一个字母的索引是0或M-1或N-1 . 如果没有，请将它们添加到队列中以便稍后查看。轮流检查所有排队的子字符串，并通过处理队列中的所有值来完成此阶段。然后检查第二个字母并继续到数组的最后一个成员。像这样，您将能够检查所有可能的单词。

它适用于我的一个这样的问题，但我不确定你是否也在寻找复杂性。

于 2012-12-03T09:53:26.493 回答
0 
import java.util.HashSet;
import java.util.Set;

 /**
 * Given a 2-dimensional array of characters and a
 * dictionary in which a word can be searched in O(1) time.
 * Need to print all the words from array which are present
 * in dictionary. Word can be formed in any direction but
 * has to end at any edge of array.
 * (Need not worry much about the dictionary)
 */
public class DictionaryWord {
private static char[][] matrix = new char[][]{
        {'a', 'f', 'h', 'u', 'n'},
        {'e', 't', 'a', 'i', 'r'},
        {'a', 'e', 'g', 'g', 'o'},
        {'t', 'r', 'm', 'l', 'p'}
};
private static int dim_x = matrix.length;
private static int dim_y = matrix[matrix.length -1].length;
private static Set<String> wordSet = new HashSet<String>();

public static void main(String[] args) {
    //dictionary
    wordSet.add("after");
    wordSet.add("hate");
    wordSet.add("hair");
    wordSet.add("air");
    wordSet.add("eat");
    wordSet.add("tea");

    for (int x = 0; x < dim_x; x++) {
        for (int y = 0; y < dim_y; y++) {
            checkAndPrint(matrix[x][y] + "");
            int[][] visitedMap = new int[dim_x][dim_y];
            visitedMap[x][y] = 1;
            recursion(matrix[x][y] + "", visitedMap, x, y);
        }
    }
}

private static void checkAndPrint(String word) {
    if (wordSet.contains(word)) {
        System.out.println(word);
    }
}

private static void recursion(String word, int[][] visitedMap, int x, int y) {
    for (int i = Math.max(x - 1, 0); i < Math.min(x + 2, dim_x); i++) {
        for (int j = Math.max(y - 1, 0); j < Math.min(y + 2, dim_y); j++) {
            if (visitedMap[i][j] == 1) {
                continue;
            } else {
                int[][] newVisitedMap = new int[dim_x][dim_y];
                for (int p = 0; p < dim_x; p++) {
                    for (int q = 0; q < dim_y; q++) {
                       newVisitedMap[p][q] = visitedMap[p][q];
                    }
                }
                newVisitedMap[i][j] = 1;
                checkAndPrint(word + matrix[i][j]);
                recursion(word + matrix[i][j], newVisitedMap, i, j);
            }
        }
    }
}

}

于 2014-11-21T04:13:01.010 回答