Добро пожаловать в такие понятия, как рекурсивность и комбинаторный взрыв :)
Из-за комбинаторного взрыва вы должны быть "умны" в этом: если пользователь хочет ввести законное слово из 20 букв, недопустимо, чтобы ваше решение "зависало", тупо пытаясь использовать десятки миллионов возможностей.
Таким образом, вы должны выполнять возврат только в том случае, если у дерева есть хотя бы одна запись для вашего префикса.
Вот способ генерировать все префиксы и использовать только при совпадении.
В этом примере я подделал трия, всегда говоря, что есть запись. Я сделал это за пять минут, так что это, безусловно, можно украсить / упростить.
Преимущество такого решения в том, что оно работает, если пользователь нажимает одну, две, три, четыре или 'n' клавиши, без необходимости изменять ваш код.
Обратите внимание, что вы, вероятно, не хотите добавлять все слова, начинающиеся с букв "x", когда их слишком много. Вам нужно найти стратегию, которая наилучшим образом соответствует вашим потребностям (подождите, пока еще несколько нажатий клавиш уменьшат количество кандидатов или добавьте наиболее распространенные совпадения в качестве кандидатов и т. Д.).
private void append( final String s, final char[][] chars, final Set<String> candidates ) {
if ( s.length() >= 2 && doesTrieContainAnyWordStartingWith( s ) ) {
candidates.add( s + "..." ); // TODO: here add all words starting with 's' instead of adding 's'
}
if ( doesTrieContainAnyWordStartingWith( s ) && chars.length > 0 ) {
final char[][] next = new char[chars.length-1][];
for (int i = 1; i < chars.length; i++) {
next[i-1] = chars[i];
}
// our three recursive calls, one for each possible letter
// (you'll want to adapt for a 'real' keyboard, where some keys may only correspond to two letters)
append( s + chars[0][0], next, candidates );
append( s + chars[0][1], next, candidates );
append( s + chars[0][2], next, candidates );
} else {
// we do nothing, it's our recursive termination condition and
// we are sure to hit it seen that we're decreasing our 'chars'
// length at every pass
}
}
private boolean doesTrieContainAnyWordStartingWith( final String s ) {
// You obviously have to change this
return true;
}
Обратите внимание на рекурсивный вызов (только при наличии соответствующего префикса).
Вот как это можно назвать: я фальсифицировал пользователя, нажимая «1», затем «2», а затем «3» (я фальсифицировал это в массиве chars char [] [], который я создал) :
public void testFindWords() {
// Imagine the user pressed 1 then 2 then 3
final char[][] chars = {
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
};
final Set<String> set = new HashSet<String>();
append( "", chars, set ); // We enter our recursive method
for (final String s : set ) {
System.out.println( "" + s );
}
System.out.println( "Set size: " + set.size() );
}
В этом примере будет создан набор, содержащий 36 совпадений, потому что я «фальсифицировал», что каждый префикс является допустимым, и что каждый префикс приводит к ровно одному слову (и я добавил «слово» только тогда, когда оно состоит как минимум из двух букв). Отсюда 3 * 3 * 3 + 3 * 3, что дает 36.
Вы можете попробовать код, он полностью работает, но вам, конечно, придется его адаптировать.
В моем поддельном примере (пользователь нажимает 1,2, а затем 3), он создает это:
cdh...
afi...
adi...
beg...
cf...
adh...
cd...
afg...
adg...
bei...
ceg...
bfi...
cdg...
beh...
aeg...
ce...
aeh...
afh...
bdg...
bdi...
cfh...
ad...
cdi...
ceh...
bfh...
aei...
cfi...
be...
af...
bdh...
bf...
cfg...
bfg...
cei...
ae...
bd...
Set size: 36
Добро пожаловать в реальное кодирование:)