То, что вы ищете, называется приближенным / нечетким поиском строки. Это действительно обширная топи c, с множеством различных реализаций, но один из моих любимых уроков для начинающих был: https://norvig.com/spell-correct.html (Обратите внимание, что это не совсем соответствует вашим требованиям, но тем не менее, хорошее чтение).
По сути, ваша проблема сводится к следующему: дать оценку, скажем, 0 - 1 всем словам в вашем словаре на основе некоторых критериев соответствия, и вернуть первые N записей на основе на этот счет. (Конечно, вам нужно быть умным в том, как это вычислить, так как для этого требуется много вычислительной мощности).
Вот краткое введение о том, как получить этот счет: Редактирование расстояния / расстояния Левенштейна дает вам «минимальная стоимость» для преобразования одной строки в другую, используя вставки / удаления / замены символов. Вы можете проверить: https://en.wikipedia.org/wiki/Levenshtein_distance или этот учебник Youtube https://www.youtube.com/watch?v=Xxx0b7djCrs. Возможно, вы захотите использовать стоимость удаления персонажа равной 0, потому что вы хотите, чтобы при поиске «Новый» Нью-Йорк / Нью-Гэмпшир имели одинаковый ранг. Вот небольшое видео на YouTube о том, как использовать расстояние Левенштейна с деревьями БК: https://www.youtube.com/watch?v=oIsPB2pqq_8.
Косинусное расстояние - еще одна мера сходства между двумя векторами, и вот хорошее объяснение: https://blog.nishtahir.com/2015/09/19/fuzzy-string-matching-using-cosine-similarity/
После небольшого поиска в Google вот старый ответ SO: Самый быстрый способ найти наиболее похожую строку для ввода?