Комментарии 7
А результат показать?
А тут точно нужно заморачиваться с префиксными деревьями? Просто построить за один проход мультимап "пачка цифр –> слово" (на стандартных библиотечных мапах) – дёшево и сердито. И код получится легкочитаемым. А оптимизировать (если потребуется) уже потом (и тут уж понадобятся бенчмарки по процу и по памяти).
Нужно ж ещё по префиксам искать возможные варианты. Как это будет в Вашем случае реализовано?
В смысле, на 26624637 вывести вначале подсказки на 2, потом на 26, потом на 266 и так далее?
Или наоборот – для 26 вывести все слова, начинающиеся с соответствующих кнопок?
для 26 вывести все слова, начинающиеся с соответствующих кнопок?
Вот это. Не все, ну часть хотя бы. Не помню, было ли такое в классическом Т9, но вроде было, по крайней мере в некоторых телефонах. Хотя оно может по другому называлось
Это уже другая задача). Для неё и входные данные другие (нужны частоты слов, чтобы подсказки были осмысленными). Тут я базово тоже использовал бы мапу, но в неё клал бы не просто списки слов, а наборы слов с рейтингом (рейтинг – функция от избытка длины и от частоты слова), не допуская переполнения набора (при необходимости отбрасывая слова с самым низким рейтингом – возможно, для этого удобно будет хранить набор в виде бинарной кучи).
Ну и тоже можно потом при необходимости мапу в префиксное дерево перевести...
Разбираем задачу T9 (predictive text)