Регулярное выражение для сходства слов "n разность букв"

Question

Предположим, у меня есть такое слово; mert .Я хочу найти все 1-буквенные комбинации различий для этого слова. Aert, ERT, мясо, Mmert, Merst, Merts и т. Д. Все применимы.Таким образом, мое регулярное выражение выглядит как

[a-z]{0,2}ert OR m[a-z]{0,2}rt OR me[a-z]{0,2}t OR mer[a-z]{0,2}

Так что для разницы n букв я просто заменяю 2 на n-1, и вы не можете получить все комбинации.

Мой вопрос такой;Есть ли более короткий способ написания этого регулярного выражения?

Спасибо

Answer 1

Для разницы в 1 букву предварительно составьте таблицу следующим образом.Создайте лексикон из 2 столбцов со словом «во втором столбце» и со следующим в первом столбце: по одной позиции за раз, уберите одну букву из слова.

Пример: «мясо» - этослово;Вот строки для него в таблице:

`col1` `col2`
------ ------
meat   meat
eat    meat
mat    meat
met    meat
mea    meat

Для «встретить» (обратите внимание на двойную букву):

meet   meet
eet    meet
met    meet  -- only needed once
mee    meet

Затем протестируйте аналогичным образом.При поиске «mert», выполните

WHERE col1 IN ('mert', 'ert', 'mrt', 'met', 'ert')

Обратите внимание, что вы получите и «мясо» и «встреча» из приведенного выше примера.Обратите также внимание на то, что произойдет с «встречается» и «встречается».

И он проверяет простые транспонирования.При поиске «meta»:

WHERE col1 IN ('meta', 'eta', 'mta', 'mea', 'met')

найдет «мясо», «встретить» (и другие слова, такие как встретил, значит, ...) Возможно, «мета» -> «значит» - это 2расстояние до буквы, ну да ладно.

Проверка ваших контрольных примеров - mert против

aert - через "ert"
ert - через "ert"
meat -- через "met"
mmert - через "mert"
merst - через "mert"
merts - через "mert"

Между тем, PRIMARY KEY(col1, col2), INDEX(col2) на этом столе.

Answer 2

Пожалуйста, проверьте это решение, у меня есть тестовый код ниже.Кажется, работает.

/**
 * Then function will return list of the words matched with nth_difference
 *
 * @param pattern search pattern
 * @param data input data
 * @param nth_difference difference
 * @return
 */
static List<String> getNthDifferenceWords(String pattern, String[] data, int nth_difference) {
    Map<Character, Integer> frequencyTable = new HashMap<>();
    List<String> matchedWords = new ArrayList<>();
    //Code complexity : O(n)
    for (int i = 0; i < pattern.length(); ++i) {
        frequencyTable.put(pattern.charAt(i), 1);
    }
    //Code complexity : O(m) where m is size of entire input;
    for (String input : data) {
        int matchCounter = 0;
        for (int j=0; j<input.length(); ++j){
            if(frequencyTable.containsKey(input.charAt(j))){
                ++matchCounter;
            }
        }
        //System.out.println("matched=" + matchCounter);
        if(input.length() <= pattern.length() && (matchCounter == pattern.length() - nth_difference)){
                matchedWords.add(input);
        }
        if((input.length() - pattern.length() == 1) && (matchCounter >= input.length() - nth_difference)){
            matchedWords.add(input);
        }
   }
    return matchedWords;
}


    public static void main(String[] args) {
    int nth_difference = 1;
    String pattern = "mert";
    String[] data = new String[]{"aert", "ert", "meat", "mmert", "merst", "merts","meritos"};
    System.out.println(getNthDifferenceWords(pattern,data,nth_difference));

    nth_difference = 2;
    pattern = "merit";
    data = new String[]{"aert", "ert", "meat", "mmert", "merst", "merts","demerit","merito", "meritos"};
    System.out.println(getNthDifferenceWords(pattern,data,nth_difference));
}