如何通过在相邻字符之间添加 space 将一个单词拆分为两个单词

Question

我正在尝试获取单词：拼写错误，并通过在相邻字符之间添加“”(space) 将单词拆分为两个单词，并希望得到结果，单词：拼写错误。任何指导都会有所帮助，一直在尝试不同的代码，但还没有看到结果。

其他建议有效的代码，仅供参考。 *请注意，注释掉的代码是我一直在尝试获得正确结果的代码。

    /**
     * Returns possible suggestions for misspelled word
     * 
     * @param tree The Trie that will be checked
     * @param word The word in trie that is checked
     */
    public static void suggest(TrieNode tree, String word) {
        Set<String> result = new HashSet<>();
        System.out.println("Suggestions: ");
        // Remove a character
        for (int i = 0; i < word.length(); ++i)
            result.add(word.substring(0, i) + word.substring(i + 1));
        // Swap two consecutive characters
        for (int i = 0; i < word.length() - 1; ++i)
            result.add(word.substring(0, i) + word.substring(i + 1, i + 2) + word.substring(i, i + 1)
                    + word.substring(i + 2));
        // Replace a character with other
        for (int i = 0; i < word.length(); ++i)
            for (char c = 'a'; c <= 'z'; ++c)
                result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i + 1));
        // Add a new character
        for (int i = 0; i <= word.length(); ++i)
            for (char c = 'a'; c <= 'z'; ++c)
                result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i));
        // Split word into pair of words by adding a " " between adjacent pairs
        // Need help here
        for (int i = 0; i < word.length(); ++i)
            for (char c = ' '; c <= ' '; ++c)
                if (search(tree, word.substring(0, i)) && search(tree, word.substring(i)) == true)
                     result.add(word.substring(0, i) + String.valueOf(c) + word.substring(i));


        ArrayList<String> res = new ArrayList<>(result);
        int j = 0;
        for (int i = 0; i < result.size(); i++)
            if (search(tree, res.get(i))) {
                if (j == 0)
                    System.out.print("[");
                System.out.print(res.get(i) + ",");
                System.out.print("");
                j++;
            }
         System.out.print("]" + "\n");
    }

Answer 1

我写了一段最小的、可运行的代码，如果在字典中找到两个单词片段，它就会拆分单词。

这是我的测试结果

miss spelling
apple

这是代码。重要的方法是splitWord方法

package com.ggl.testing;

import java.util.ArrayList;
import java.util.List;

public class DoubleWord implements Runnable {

    public static void main(String[] args) {
        new DoubleWord().run();
    }

    @Override
    public void run() {
        Dictionary dictionary = new Dictionary();
        System.out.println(splitWord("missspelling", dictionary));
        System.out.println(splitWord("apple", dictionary));
    }

    public String splitWord(String word, Dictionary dictionary) {
        for (int index = 1; index < word.length(); index++) {
            String prefix = word.substring(0, index);
            if (dictionary.isWordInDictionary(prefix)) {
                String suffix = word.substring(index);
                if (dictionary.isWordInDictionary(suffix)) {
                    return prefix + " " + suffix;
                }
            }
        }

        return word;
    }

    public class Dictionary {
        private List<String> words;

        public Dictionary() {
            this.words = setWords();
        }

        public boolean isWordInDictionary(String word) {
            return words.contains(word);
        }

        private List<String> setWords() {
            List<String> words = new ArrayList<>();
            words.add("apple");
            words.add("miss");
            words.add("spelling");
            words.add("zebra");

            return words;
        }
    }

}

Answer 2

首先有几件事...

这条线很疯狂：

for (char c = ' '; c <= ' '; ++c)

它将恰好迭代一次，相当于：

char c = ' ';

您正在重新发明轮子，尝试通过交换字符然后替换字符来查找有效单词：阅读有关 Levenshtein distance 的内容，实施该算法，然后根据输入的 Levenshtein 距离对字典进行排序以查找"best matches"，应按最大 Levenshtein 距离进行过滤 - 也许 3 是一个很好的起点（测试您的代码并查看结果是否合理）。

你的 TrieNode 应该有一个 search() 方法，而不是你的 search() 方法接受一个 trie 和一个词，但这更多是设计问题，并不是你最大的问题问题。

现在，关于您的实际问题，尝试拆分输入很复杂，但 "answer" 是：

遍历输入中字母之间的所有位置，并将每个 "half" 通过与输入相同的过程，除了你不应该进行嵌套拆分，结合每个组合每半的建议，然后 return 所有独特建议组合的集合。

但是，这样做会产生 "very large" 个建议，因此无法扩展，因此您可能不应该这样做。

如何通过在相邻字符之间添加 space 将一个单词拆分为两个单词

how to split a word into two words by adding a space between adjacent characters

java

spell-checking

trie