java - 将单词逐个字符递归地添加到 LinkedHashMap

Question

我正在尝试编写一个可以在其中输入单词的类，并且将从输入的单词创建一棵字符树。然后可以检查树中是否存在某个单词。我的问题是，我只能让它保存任何单词中的一个字符 - 如果一个单词有多个字符，则只保存第一个字符(我很确定 contains 方法是正确的)。这是我的代码，它显然有问题，但我不知道是什么:

public class Dictionary {

  private Map<Character, DictionaryTree> children = new LinkedHashMap<>();
  private boolean endOfWord;

  DictionaryTree() {
    endOfWord = false;
  }

  void insert(String word) {
    if (!contains(word)) {
      DictionaryTree newDictionaryTree = new DictionaryTree();
      if (word.length() > 1) {
        newDictionaryTree.insert(word.substring(1, word.length()));
      } else if (word.length() == 1) {
        newDictionaryTree.endOfWord = true;
      }
      children.put(word.charAt(0), newDictionaryTree);
    }
  }

  boolean contains(String word) {
    if (word.length() > 0) {
      // Check if first letter is a child node
      if (children.containsKey(word.charAt(0))) {
        if (word.length() > 1) {
          DictionaryTree extractedDictionaryTree = children.get(word.charAt(0));
          extractedDictionaryTree.contains(word.substring(1, word.length()));
        }
        // If only one character left, check if end of word
        else if (children.get(word.charAt(0)).endOfWord == true) {
          return true;
        } else {
          return false;
        }
      }
      return false;
    }

    return false;
  }
}

任何帮助将不胜感激。

Answer 1

根据您的要求，您想要搜索一个单词，无论它是否存在。 您将使用 LinkedHashmap 来实现它，但您可以尝试使用 Trie 数据结构。它提供了插入和搜索字符串或任何数据的有效方法。

源代码引用自GeeksForGeeks

                   root
                /   \    \
                t   a     b
                |   |     |
                h   n     y
                |   |  \  |
                e   s  y  e
             /  |   |
             i  r   w
             |  |   |
             r  e   e
                    |
                    r

实现:

// Java implementation of search and insert operations
// on Trie
public class Trie {

    // Alphabet size (# of symbols)
    static final int ALPHABET_SIZE = 26;

    // trie node
    static class TrieNode
    {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];

        // isEndOfWord is true if the node represents
        // end of a word
        boolean isEndOfWord;

        TrieNode(){
            isEndOfWord = false;
            for (int i = 0; i < ALPHABET_SIZE; i++)
                children[i] = null;
        }
    };

    static TrieNode root; 

    // If not present, inserts key into trie
    // If the key is prefix of trie node, 
    // just marks leaf node
    static void insert(String key)
    {
        int level;
        int length = key.length();
        int index;

        TrieNode pCrawl = root;

        for (level = 0; level < length; level++)
        {
            index = key.charAt(level) - 'a';
            if (pCrawl.children[index] == null)
                pCrawl.children[index] = new TrieNode();

            pCrawl = pCrawl.children[index];
        }

        // mark last node as leaf
        pCrawl.isEndOfWord = true;
    }

    // Returns true if key presents in trie, else false
    static boolean search(String key)
    {
        int level;
        int length = key.length();
        int index;
        TrieNode pCrawl = root;

        for (level = 0; level < length; level++)
        {
            index = key.charAt(level) - 'a';

            if (pCrawl.children[index] == null)
                return false;

            pCrawl = pCrawl.children[index];
        }

        return (pCrawl != null && pCrawl.isEndOfWord);
    }

    // Driver
    public static void main(String args[])
    {
        // Input keys (use only 'a' through 'z' and lower case)
        String keys[] = {"the", "a", "there", "answer", "any",
                         "by", "bye", "their"};

        String output[] = {"Not present in trie", "Present in trie"};


        root = new TrieNode();

        // Construct trie
        int i;
        for (i = 0; i < keys.length ; i++)
            insert(keys[i]);

        // Search for different keys
        if(search("the") == true)
            System.out.println("the --- " + output[1]);
        else System.out.println("the --- " + output[0]);

        if(search("these") == true)
            System.out.println("these --- " + output[1]);
        else System.out.println("these --- " + output[0]);

        if(search("their") == true)
            System.out.println("their --- " + output[1]);
        else System.out.println("their --- " + output[0]);

        if(search("thaw") == true)
            System.out.println("thaw --- " + output[1]);
        else System.out.println("thaw --- " + output[0]);

    }
}

希望对你有帮助!!!