逐个字符递归地向链接哈希映射添加单词

Question

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

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]);
}
}

希望对您有所帮助!!