string - 查找字典中最长的单词，这样就可以通过将单个字符连续添加到前一个单词来构建它

Question

我发现以下问题和决定者分享了一种可能的解决方案。

问题：

假设您有一个基于具有固定字符数的字母表的单词词典。请编写一个方法/函数来查找字典中最长的单词，以便可以通过将单个字符连续添加到字典中的现有单词（在任何位置）来构建它。

例如，“a” -> “at” -> “cat” -> “chat” -> “chart”。

Answer 1

这是动态编程的一个很好的例子。我会查看本书http://www.cs.berkeley.edu/~vazirani/algorithms/all.pdf的动态编程部分。他从非常简单的例子开始，然后以一种很有意义的方式构建复杂的例子。

DP 面临的挑战是构建在多项式时间内运行的解决方案。大多数 DP 解决方案都是 O(n^2)，这仍然优于指数（例如尝试字典中的每个组合）。该解决方案将涉及使用数组来构建信息，这些信息将继续建立在自身之上并导致有答案的东西

Answer 2

我从这篇文章中提出了解决问题的想法：Successive added of char to get the long word in the dictionary

基本上，它遍历字典中的每个单词并通过递归地从字符串中删除字符来生成路径，直到新单词不在字典中或大小为 1。如果最后一个单词是目标字符，我找到了可能的最大路径。假设字典以哈希映射的形式给出，运行时间为 O(n*k^2)，其中 n 是字典中的单词数，k 是最大字符串的长度（最坏情况）。我相信它可以通过修剪一些单词来优化，例如。不包含目标字符的单词。

它返回一组字符串（以简化编码）。例如。如果目标字符是'a'，此函数返回：[tamped, stamped, ta, a, tape, tap, tapeed, stampedes, stampede]

我将不胜感激有关此解决方案的任何想法。

    public static Set<String> findLongestPath(char targetChar, 
Set<String> dictionary) {

        Set<String> maxPath = new HashSet<String>();

        for (String word: dictionary) {
            Set<String> currentPath = findPath(word, dictionary, targetChar);
            if (maxPath.size() < currentPath.size()) {
                maxPath = currentPath;
            }
        }
        return maxPath;
    }

    public static Set<String> findPath(String word, Set<String> dictionary, char targetChar) {
        String targetCharStr = "" + targetChar;
        Set<String> path = new HashSet<String>();

        if (word.length() == 1) {
            path.add(word);
        } else if (dictionary.contains(word)) {
            for (int i = 0; i < word.length(); i++) {
                //remove one character from a word and try to find path for it
                String subWord = word.substring(0, i) + word.substring(i + 1);
                Set<String> deepPath = findPath(subWord, dictionary, targetChar);
                //stop if path contains word with a single character wich is a target character
                if (deepPath.contains(targetCharStr)) {
                    path.add(word);
                    path.addAll(deepPath);
                    break;
                }
            }
        }
        return path;
    }

And here is small driver:

    public static void main(String[] args) throws Exception {

        char targetChar = 'a';
        Set<String> dictionary = new HashSet<String>();
        BufferedReader dictionaryFile = new BufferedReader(new FileReader("/usr/share/dict/words"));
        String line;
        while ((line = dictionaryFile.readLine()) != null) {
            if (line.contains("'")) { continue; }
            dictionary.add(line.toLowerCase().trim());
        }
        dictionaryFile.close();

        System.out.println(findLongestPath(targetChar, dictionary));    
    }