6

最近の就職の面接で、私は次の問題の解決策を提供するように頼まれました。

文字列s（スペースなし）と辞書を指定して、文字列を構成する辞書内の単語を返します。

たとえば、s= peachpie, dic= {peach, pie}, result={peach, pie}。

私はこの問題の決定のバリエーションを尋ねます：

s辞書内の単語で構成できる場合はreturn yes、それ以外の場合はreturn no。

これに対する私の解決策は、バックトラック（Javaで書かれた）でした

public static boolean words(String s, Set<String> dictionary)
{
    if ("".equals(s))
        return true;

    for (int i=0; i <= s.length(); i++)
    {
        String pre = prefix(s,i); // returns s[0..i-1]
        String suf = suffix(s,i); // returns s[i..s.len]
        if (dictionary.contains(pre) && words(suf, dictionary))
            return true;
    }
    return false;
}

public static void main(String[] args) {
    Set<String> dic = new HashSet<String>();
    dic.add("peach");
    dic.add("pie");
    dic.add("1");

    System.out.println(words("peachpie1", dic)); // true
    System.out.println(words("peachpie2", dic)); // false
}

このソリューションの時間計算量はどれくらいですか？forループで再帰的に呼び出していますが、辞書にあるプレフィックスに対してのみ呼び出しています。

何か案は？

4

3 に答える 3

5

プログラムが完了するまでに少なくとも指数関数的な時間がかかるケースを簡単に作成できます。単語を取りましょうaaa...aaab、ここでaは何n度も繰り返されます。辞書には、aとの 2 つの単語のみが含まれますaa。

b最後に、関数が一致するものを決して見つけないこと、したがって途中で終了しないことを確認してください。

実行ごとに、withとwordsの 2 つの再帰呼び出しが生成されます。したがって、実行時間はフィボナッチ数のように増加します。（カウンターを挿入することで確認できます。）したがって、複雑さは確かに多項式ではありません。(そして、これは考えられる最悪の入力でさえありません)suffix(s, 1)suffix(s, 2)t(n) = t(n - 1) + t(n - 2)

しかし、 Memoizationを使用すると、ソリューションを簡単に改善できます。関数の出力はwords、元の文字列のどの位置から開始するかという 1 つのことのみに依存することに注意してください。文字列がabcdefgありwords(5)、それが呼び出された場合、それがどのように正確abcdeに構成されているかは問題ではありません ( ab+c+deora+b+c+d+eまたは何か他のものとして)。words("fg")したがって、毎回再計算する必要はありません。
プリミティブバージョンでは、これは次のように行うことができます

public static boolean words(String s, Set<String> dictionary) {
    if (processed.contains(s)) {
        // we've already processed string 's' with no luck
        return false;
    }

    // your normal computations
    // ...

    // if no match found, add 's' to the list of checked inputs
    processed.add(s);
    return false;
}

PS それでも、 に変更words(String)することをお勧めしますwords(int)。このようにして、結果を配列に格納し、アルゴリズム全体を DP に変換することもできます (これにより、はるかに簡単になります)。

edit 2
仕事以外にやることはあまりないので、ここに DP (動的プログラミング) ソリューションを示します。上と同じ考え方。

    String s = "peachpie1";
    int n = s.length();
    boolean[] a = new boolean[n + 1];
    // a[i] tells whether s[i..n-1] can be composed from words in the dictionary
    a[n] = true; // always can compose empty string

    for (int start = n - 1; start >= 0; --start) {
        for (String word : dictionary) {
            if (start + word.length() <= n && a[start + word.length()]) {
                // check if 'word' is a prefix of s[start..n-1]
                String test = s.substring(start, start + word.length());
                if (test.equals(word)) {
                    a[start] = true;
                    break;
                }
            }
        }
    }

    System.out.println(a[0]);
于 2010-12-30T14:17:10.923 に答える
1

これは、文字列を単語に分解する方法の総数をカウントする動的プログラミング ソリューションです。分解数が正の場合、文字列は分解可能であるため、元の問題は解決します。

def count_decompositions(dictionary, word):
    n = len(word)
    results = [1] + [0] * n
    for i in xrange(1, n + 1):
        for j in xrange(i):
            if word[n - i:n - j] in dictionary:
                results[i] += results[j]
    return results[n]

ストレージ O(n)、実行時間 O(n^2)。

于 2010-12-30T15:00:25.820 に答える
0

すべての文字列のループは。を取りnます。すべてのサフィックスとプレフィックスを見つけるにはn + (n - 1) + (n - 2) + .... + 1（n最初の呼び出しのwords場合、(n - 1)2番目の呼び出しの場合など）、次のようになります。

n^2 - SUM(1..n) = n^2 - (n^2 + n)/2 = n^2 / 2 - n / 2

複雑さの理論では、これはn^2と同等です。

通常の場合はHashSetに存在するかどうかをチェックするのはシータ（1）ですが、最悪の場合はO（n）です。

したがって、アルゴリズムの通常の複雑さはTheta（n ^ 2）であり、最悪の場合はO（n ^ 3）です。

編集：再帰と反復の順序を混同したので、この答えは間違っています。実際には、時間は指数関数的に依存しますn（たとえば、フィボナッチ数の計算と比較してください）。

さらに興味深いのは、アルゴリズムをどのように改善するかという問題です。従来、文字列操作には接尾辞木が使用されていました。文字列を使用して接尾辞木を作成し、アルゴの開始時にすべてのノードを「追跡されていない」としてマークすることができます。次に、セット内の文字列を調べ、ノードが使用されるたびに、そのノードを「追跡済み」としてマークします。セット内のすべての文字列がツリーで見つかった場合、元の文字列にはセットのすべてのサブ文字列が含まれていることを意味します。また、すべてのノードが追跡対象としてマークされている場合、その文字列はセットのサブ文字列のみで構成されていることを意味します。

このアプローチの実際の複雑さは、ツリー構築アルゴリズムなどの多くの要因に依存しますが、少なくとも問題をいくつかの独立したサブタスクに分割できるため、最も高価なサブタスクの複雑さによって最終的な複雑さを測定できます。

于 2010-12-30T14:56:31.973 に答える