Совпадение подстроки в строке с допустимым отклонением в 1 символ (в JS)

Question

На этот вопрос успешно ответили для языка Си, но пока не для JS.

Напишите функцию, которая может найти, если строка является подстрокой другой.Обратите внимание, что несоответствие одного символа следует игнорировать.

A mismatch can be an extra character: ’dog’ matches ‘xxxdoogyyyy’  
A mismatch can be a missing character: ’dog’ matches ‘xxxdgyyyy’ 
A mismatch can be a different character: ’dog’ matches ‘xxxdigyyyy’

Существующие модули нечеткого поиска слишком сложны и непредсказуемы для этого конкретного случая.Как написать такую ​​функцию в JS?

Примечание: Вот оригинальный вопрос и принятое решение @IVlad (2016) на языке C:

int findHelper(const char *str, const char *substr, int mustMatch = 0)
{
    if ( *substr == '\0' )
        return 1;

    if ( *str == '\0' )
        return 0;

    if ( *str == *substr )
        return findHelper(str + 1, substr + 1, mustMatch);
    else
    {
        if ( mustMatch )
            return 0;

        if ( *(str + 1) == *substr )
            return findHelper(str + 1, substr, 1);
        else if ( *str == *(substr + 1) )
            return findHelper(str, substr + 1, 1);
        else if ( *(str + 1) == *(substr + 1) )
            return findHelper(str + 1, substr + 1, 1);
        else if ( *(substr + 1) == '\0' )
            return 1;
        else
            return 0;
    }
}

int find(const char *str, const char *substr)
{
    int ok = 0;
    while ( *str != '\0' )
        ok |= findHelper(str++, substr, 0);

    return ok;
}


int main()
{
    printf("%d\n", find("xxxdoogyyyy", "dog"));
    printf("%d\n", find("xxxdgyyyy", "dog"));
    printf("%d\n", find("xxxdigyyyy", "dog"));
}

Answer 1

вы можете сделать это с помощью генератора регулярных выражений, как это

Редактировать: добавить еще тесты

Редактировать # 2: как подсказывает @amadan, добавить?.? для сценария вставки символа

var txtToSearch = 'dog';
function find(txt,src) {
  // generate regex for all possibilities. for this case, it will generate "d?.?og|do?.?g|dog?.?" -> double .? are for 1 char insertion 
  var re = new RegExp(txt.split('').map(function(a,b,c){ return txt.substr(0, b)+a+'?.?'+ txt.substr(b+1);}).join('|'),'gi');
  return src.match(re)!=null
}

// test cases
console.log('"'+txtToSearch+'" in : xxxdoogyyyy -> '+find(txtToSearch,'xxxdoogyyyy'));
console.log('"'+txtToSearch+'" in : xxxdgyyyy -> '+find(txtToSearch,'xxxdgyyyy'));
console.log('"'+txtToSearch+'" in : xxxdigyyyy -> '+find(txtToSearch,'xxxdigyyyy'));
console.log('"'+txtToSearch+'" in : xxxggoodyyyy -> '+find(txtToSearch,'xxxggoodyyyy'));

// another test case
console.log('"great" in : xxzzgreetsxxy -> '+find('great','xxzzgreetsxxy'));
console.log('"greetings" in : xxzzgreextingssxxy-> '+find('greetings','xxzzgreextingssxxy'));