hsc>для пар "Amélie" и "Amelie", "Ёлка" и "Елка" — true
hsc>для пар "Amolie" и "Amelie", "Oлка" и "Елка" — false

Тогда загоняем обе строки в транслит и сравниваем результаты.
Это может сделать ICU http://userguide.icu-project.org/transforms/general#TOC-Using-Transliterators