Самый быстрый алгоритм проверки набора слов в телефонной цифре

Question

Например, у меня есть массив ['bab', 'col', 'stro'] ...

IN     OUT
222    bab
7876   stro
999    <empty>        no match

Есть ли какой-нибудь алгоритм для решения этой проблемы лучше, чем O (n ^2)

Answer 1

Используйте std::vector<std::string> words для представления ввода.

std::vector<std::string> S;
// First convert strings to (string)numbers.
for(auto word in words){
    std::string s;
    for(auto c in word)
        switch (c)
        {
            case 'a':case 'b': case 'c'
            s += '1'; break;
            case 'd':case 'e': case 'f'
            s += '2'; break;
            ...
        }
    S.push_back(s);
}

// Now S has corresponding numbers for each string
std::string input;
std::cin >> input;
// Find the number string match on a given input. You can do iteratively search here to find all.
if (S.find(input) == S.end())
    std::cout << "Does not exist" << endl;
else
    std::cout << words[S.find(input) - S.begin()] << endl;

Это простой фрагмент в C ++, и вы сможете конвертировать в любые другие языки.

Строго говоря,не существует O(n) алгоритм, так как он должен зависеть от максимальной длины строк.Этот алгоритм работает в O(kn), где k - максимальная длина всех строк.

Answer 2

Я думаю, вам следует использовать TRIE Структура данных для реализации (каждая запись имени и номера телефона - один лист).TRIE - это упорядоченная древовидная структура данных, которая использует строки в качестве ключей.проверить это статья

Answer 3

предварительно обрабатывает ваш список в таблице перевода, причем каждое слово имеет свой числовой эквивалент.Это упрощает поиск.

dial_num = [
    'a' : 2,
    'b' : 2,
    'c' : 2.
    'd' : 3,
    ...
]

Затем переведите каждое из ваших слов:

dial_word = [
    222 : 'bab',
    264 : 'col',
    7876 : 'stro'
    ...
]

Это задание O (N) по длине массива в символах.Теперь у вас есть простой поиск (линейный или логарифм) для данного числа.Если вы хотите дополнительно предварительно обработать dial_word как хеш-таблицу, у вас будет O (1) поиск.