Печатать Компоненты дерева

Question

Я новичок в java, и я хочу создать очень простой Программа «Слово завершения». Я буду читать в файле словаря и рекурсивно добавлять слова в массив узлов (размер 26). Я считаю, что мне удалось сделать это успешно, но я не уверен, как пройти и распечатать матчи. Для тестирования я просто вставляю 2 слова в данный момент, вызывая функцию. Как только все будет работать, я добавлю метод для чтения файла и удаления мусора из этого слова.

Например: Если слова «тест» и «тестер» находятся внутри дерева, а пользователь вводит «tes», он должен отображать «тест» и «тестер».

Если кто-нибудь может рассказать мне, как пройти и распечатать матчи (если есть), я был бы очень признателен. Полный код приведен ниже.

Спасибо

Answer 1

Что вы реализовали is called"trie". Вы можете посмотреть на существующие реализации.

То, что вы использовали для хранения дочерних узлов, называется хеш-таблицей, и вы можете использовать стандартные реализации и не выполнять его самостоятельно, если у вас нет очень-очень конкретных причин для этого. У вашей реализации есть некоторые ограничения (диапазон символов, например).

---

Я думаю, ваш код содержит ошибку в методе has:

... 
else if (letter[val].flag==true || word.length()==1) { 
    return true; 
} 

Если этот метод предназначен для возврата верно, если есть строки, начинающиеся с word, то он не должен проверить flag. Если он должен возвращать true, если есть только точное совпадение, он не должен проверять word.length().

И, наконец, решение вашего вопроса: не оптимальное, но самым простым решением было бы сделать метод, который берет строку и возвращает узел, соответствующий этой строке, и метод, который составляет все слова из узла. Что-то вроде этого (не проверено):

class Tree { 

    ... 
    public List<String> matches(CharSequence prefix) { 
     List<String> result = new ArrayList<>(); 
     if(r != null) { 
      Node n = r._match(prefix, 0); 
      if(n != null) { 
       StringBuilder p = new StringBuilder(); 
       p.append(prefix); 
       n._addWords(p, result); 
      } 
     } 
     return result; 
    } 
} 

class Node { 

    ... 
    protected Node _match(CharSequence prefix, int index) { 
     assert index <= prefix.length(); 
     if(index == prefix.length()) { 
      return this; 
     } 
     int val = prefix.charAt(index) - 'a'; 
     assert val >= 0 && val < letter.length; 
     if (letter[val] != null) { 
      return letter[val].match(prefix, index+1); 
     } 
     return null; 
    } 

    protected void _addWords(StringBuilder prefix, List<String> result) { 
     if(this.flag) { 
      result.add(prefix.toString()); 
     }  
     for(int i = 0; i<letter.length; i++) { 
      if(letter[i] != null) { 
       prefix.append((char)(i + 'a')); 
       letter[i]._addWords(prefix, result); 
       prefix.delete(prefix.length() - 1, prefix.length()); 
      } 
     } 
    } 
} 

Answer 2

Может быть рискованное здесь, но почему бы вам не попробовать регулярных выражений здесь? Насколько я понимаю, вы хотите, чтобы соответствовать слова к списку слов:

List<String> getMatches(List<String> list, String regex) { 

    Pattern p = Pattern.compile(regex); 
    ArrayList<String> matches = new ArrayList<String>(); 

    for (String s:list) { 
    if (p.matcher(s).matches()) { 
     matches.add(s); 
    } 
    } 

    return matches 
}