-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

这是我解决算法的方法。

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 回答
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 回答