-4

提供された単語のリストを使用して文字列を解読する方法。

例えば：

List of words in Dictionary:

Hi
Hello
Welcome
to
Stack
Overflow

Input String:

WelcometoStackOverflow

Output must be (with space added):

Welcome to Stack Overflow

リストにない単語については、NULL印刷する必要があります。

Input String:

StackOverflowWelcomeYou

Output must be:

NULL

実装方法に関する提案やアイデアはありますか...??

4

2 に答える 2

1

最大の課題は、入力文字列を分割する方法であり、OP が詳細を提供するまで、すべての回答/コメントは何らかの仮定に基づいています。

この回答では、入力が最初の文字が大文字のキャメルケース文字列であると仮定しています。

public class CheckDict {
    static Set<String> dict = new HashSet<String>(Arrays.asList(new String[] 
                              {"Hi", "Hello", "Welcome", "To", "Stack", "Overflow"}));

    public static void main(String[] args) {
        System.out.println("Test 1: " + findDict("WelcomeToStackOverflow"));
        System.out.println("Test 2: " + findDict("StackOverflowWelcomeYou"));
    }

    static String findDict(String str) {
        // split the string when we encounter an upper case letter except at start
        String[] arr = str.split("(?<!^)(?=[A-Z])");
        StringBuilder output = new StringBuilder(arr[0]);
        for (int i=1; i< arr.length; i++) {
            if (!dict.contains(arr[i]))
                return null;
            else
                output.append(' ').append(arr[i]);
        }
        return output.toString();
    }
}

出力：

Test 1: Welcome To Stack Overflow
Test 2: null
于 2013-07-20T07:51:56.107 に答える
1

これが、アルゴリズムを解決するために私がとるアプローチです。

1) ディクショナリを償却定数時間ルックアップ用のハッシュ マップ構造にロードするか、対数時間ルックアップ用の順序付きマップにロードします。

2) 辞書で一致が見つかるまで、可能な部分文字列 [0, i] を反復処理します。

a) 一致が見つかった場合、入力文字列からこの単語を削除し、最終的な回答を報告するために ArrayList 構造に格納します

b) 一致が見つからない場合、または i が文字列のサイズと等しい場合は null を報告します

3) 文字列の配列リストを反復処理し、スペースで区切られたリストを出力します

L と呼ぶルックアップ時間に応じて、このアルゴリズムは O(n * L) を取る必要があります。ここで、n は入力文字列の文字数です。ルックアップに償却された一定の時間がかかる場合、たとえばハッシュマップの場合、O(n) になります。それ以外の場合は、O(n log D) で実行できます。ここで、D は辞書のサイズです。

于 2013-07-20T07:17:42.650 に答える