15

面接で次の質問をされました。この質問へのアプローチ方法がわかりませんでした。私を案内してください。

質問: 文字列を 2 つの文字列に分割できるかどうかを知るにはどうすればよいですか? たとえば、ブレッドバナナはパンとバナナに分割できますが、ブレッドバナンは分割できません。すべての有効な単語を含む辞書が提供されます。

4

6 に答える 6

13

辞書に載っている単語を試してみると、検索が速くなります。入力文字列の次の文字に従ってツリーを検索します。ツリー内に単語が見つかったら、入力文字列内のその単語の後の位置から再帰的に開始します。入力文字列の末尾に到達すると、断片化の可能性が 1 つ見つかりました。行き詰まった場合は、戻って再帰的に別の単語を試してください。

編集: 申し訳ありませんが、単語が 2 つしかないという事実を見逃していました。この場合、再帰の深さを 2 に制限します。

2 ワードの疑似コードは次のようになります。

T = trie of words in the dictionary
for every word in T, which can be found going down the tree by choosing the next letter of the input string each time we move to the child:
    p <- length(word)
    if T contains input_string[p:length(intput_string)]:
        return true
return false

トライ (子の ASCII インデックス) 内の子ノードに移動できると仮定するとO(1)、 で入力文字列のすべてのプレフィックスを見つけることができますO(n+p)。ここpで、 はプレフィックスの数、およびn入力の長さです。この上限は ですO(n+m)。ここmで、 は辞書内の単語の数です。含まれているかどうかをチェックすると、単語の長さはO(w)どこwにあり、上限は になりますm。アルゴリズムの時間の複雑さは、見つかったすべての単語の間の最初のフェーズで分散されるO(nm)ためです。O(n)

しかし、最初のフェーズでは単語しか見つからないためn、複雑さも に制限されO(n^2)ます。したがって、検索の複雑さは次のようになります。その前に、辞書内の単語の長さの合計であるO(n*min(n, m)) を取るトライを構築する必要があります。すべての単語の最大長は であるため、これの上限は です。O(s)sO(n*m)n

于 2013-03-06T07:28:13.690 に答える
4

辞書を調べて、すべての用語を部分文字列として元の用語（「breadbanana」など）と比較します。最初の用語が最初の部分文字列と一致する場合は、元の検索用語から最初の用語を切り取り、次の辞書エントリを元の用語の残りの部分と比較します...

Javaでそれを説明しようとしましょう：例えば

    String dictTerm = "bread";
    String original = "breadbanana";

    // first part matches
    if (dictTerm.equals(original.substring(0, dictTerm.length()))) {
        // first part matches, get the rest
        String lastPart = original.substring(dictTerm.length());

        String nextDictTerm = "banana";

        if (nextDictTerm.equals(lastPart)) {
            System.out.println("String " + original +
                " contains the dictionary terms " +
                dictTerm + " and " + lastPart);
        }
    }
于 2013-03-06T07:39:39.800 に答える
1

最も簡単な解決策：

連続する文字のすべてのペア間で文字列を分割し、両方の部分文字列 (分割ポイントの左側と右側) が辞書に含まれているかどうかを確認します。

于 2013-03-06T07:24:47.490 に答える
0 
public boolean canBeSegmented(String s) {
    for (String word : dictionary.getWords()) {
        if (s.contains(word) {
            String sub = s.subString(0, s.indexOf(word)); 
            s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1);
        }

        return s.equals("");
    }
}

このコードは、指定された文字列を完全にセグメント化できるかどうかをチェックします。辞書からの単語が文字列内にあるかどうかをチェックし、それをサブトラックします。プロセスでセグメント化する場合は、減算されたsemententを単語内の順序で並べ替える必要があります。

たった2つの単語で簡単になります。

public boolean canBeSegmented(String s) {
    boolean wordDetected = false;

    for (String word : dictionary.getWords()) {
        if (s.contains(word) {
            String sub = s.subString(0, s.indexOf(word)); 
            s = sub + s.subString(s.indexOf(word)+word.length(), s.length()-1);

            if(!wordDetected) 
                wordDetected = true;
            else 
                return s.equals("");
        }

        return false;
     }
}

このコードは1つの単語をチェックし、文字列に別の単語があり、これら2つの単語だけがある場合は、trueを返します。それ以外の場合はfalseを返します。

于 2013-03-06T07:29:25.967 に答える
0

1つのアプローチは次のとおりです。

Put all elements of dictionary in some set or listcontains&関数を 使用substringして、辞書に一致する単語を削除できるようになりました。最後の文字列が null の場合 -> 文字列をセグメント化できます。そうでない場合はセグメント化できません。カウントもお任せください。

于 2013-03-06T07:27:42.297 に答える
0

これは単なるアイデアです。必要に応じてより適切に実装できます

package farzi;

import java.util.ArrayList;

public class StringPossibility {
    public static void main(String[] args) {
        String str = "breadbanana";
        ArrayList<String> dict = new ArrayList<String>();
        dict.add("bread");
        dict.add("banana");
        for(int i=0;i<str.length();i++)
        {
            String word1 = str.substring(0,i);
            String word2 = str.substring(i,str.length());
            System.out.println(word1+"===>>>"+word2);
            if(dict.contains(word1))
            {
                System.out.println("word 1 found : "+word1+" at index "+i);
            }
            if(dict.contains(word2))
            {
                System.out.println("word 2 found : "+ word2+" at index "+i);
            }
        }

    }

}
于 2013-03-06T08:36:37.713 に答える