7

最近、このインタビューの質問に出くわしました。

文字の 2 次元配列と、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

注：ここで「卵」は配列の端で終わっていないため、辞書の単語ではありません。

以前にも同様の質問を見たことがありますが、この種の問題を解決するための優れたアルゴリズムを思いつくことはできませんでした。この種の問題 (文字の配列から単語を形成する) にアプローチする方法についてのヘルプは非常に役立ちます。

(私が考えることができる唯一の方法は、2D 配列内の文字のすべての可能な順列を見つけ、それが配列の端で終わるかどうかを確認し、順列が O(1) の辞書からの有効な単語であるかどうかを確認することです)時間）

4

4 に答える 4

3

配列をグラフに変換して、各セル[i,j] のエッジが 4 つの隣接セルのそれぞれと共有されるようにします[i+1,j], [i-1,j], [i,j+1], [i,j-1]。次に、各配列エッジセルで DFS を実行し、辞書に逆の単語が含まれているかどうかを確認し続けます。

于 2012-12-03T09:57:53.283 に答える
2

文字を一度しか使用できないことについては何も言及していませんでした。したがって、この制限がなければ、「k (またはそれ以上) の異なる単語を生成できますか?」という問題があります。未定です。1 .

（要素ごとの「訪問」の数に制約があるため、可能性の数は有限であり、主張と証明はもちろん成立しません）。

証明: 終了アルゴリズムが 1つ以上の異なる入力に対して返されるかどうかを決定できる
アルゴリズムがないことが知られています。（必要に応じて後でこの主張の引用を探します。今のところ私を信じてください）。ABtruek

以上の生成された単語があるかどうかを判断するアルゴリズムAが与えられた場合、「true」を生成する異なる入力があるかどうかを判断できることを示します。kk

  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 が true と答えた場合 ->n受け入れられた単語が複数ある場合 -> nB に true を返す異なる入力がある場合 (辞書の定義であり、すべての入力を配列で生成できるため) -> 問題の答えは true であることに注意してください。 .
(アルゴリズムが false と答えた場合、証明は同様です)。

QED

結論:
配列内の文字を 1 回以上繰り返すことができる場合 (または正確には - 無制限の回数) 、問題は辞書に関する情報なしでは解決できません。

(1) 決定不能問題とは、100% のケースで TRUE/FALSE を正しく答えることができるアルゴリズムがない問題です。すべてのアルゴリズムについて、アルゴリズムが無限ループで「スタック」する場合があります (または間違った答えをする）。「決定不能」な問題の最も一般的なものは停止問題Aです。つまり、任意のアルゴリズムを取り、何らかの入力で停止したB場合に応答できるアルゴリズムはありません。Bw

于 2012-12-03T10:58:57.600 に答える
0

私の解決策は次のとおりです。

M*N 配列があり、単語の検索に制限はないと思います。たとえば、'rood' と 'door' は、互いに逆になっている 2 つの異なる単語です。

最初の文字 (左、上) から開始します。この場合は「a」です。そして、辞書に単語があるかどうかをチェックします（「ae」と「af」で始まる単語があるとします）それらがすでに単語であるかどうか、最後の文字のインデックスが0またはM-1またはN-1であるかどうかを確認します. そうでない場合は、キューに追加して後で確認します。順番に、このようにキューに入れられたすべての部分文字列をチェックし、キュー内のすべての値を処理してこのフェーズを終了します。次に、2 番目の文字を確認し、配列の最後のメンバーまで進みます。このように、可能なすべての単語を確認できます。

このような私の問題の 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 に答える