Сегодня я собираюсь объяснить, как решить алгоритм All Matching Substrings. All Matching Substrings — это алгоритм, который включает в себя поиск каждой совпадающей подстроки между двумя строками и возвращение их в массив. Обе строки будут одним словом без пробелов. Сопоставление не зависит от регистра, результирующий массив должен состоять из строк нижнего регистра. Если совпадающих подстрок нет, функция должна просто вернуть false.
Например:
с входами «BUICK» и «squid» возврат будет [ «u», «ui», «i»]
Давайте сломаем это. Для начала мы можем использовать строчные буквы для обеих наших входных строк, чтобы выполнить требование нечувствительности к регистру.
function matchingSubStrings(a, b) { const strA = a.toLowerCase() const strB = b.toLowerCase() }
Теперь давайте создадим пустой массив, который мы заполним совпавшими подстроками.
function matchingSubStrings(a, b) { const strA = a.toLowerCase() const strB = b.toLowerCase() let output = [] }
Теперь нам нужно перебрать каждую возможную подстроку одной из наших строк и проверить, включена ли она в другую строку. Мы можем изолировать каждую подстроку с помощью метода разделения строки. Метод разбиения строки принимает 2 аргумента: индекс первого символа, который нужно включить в разбиение, и индекс, до которого разбиение будет включать символы (только символ с этим индексом не будет включен в разбиение). Мы можем получить эти индексы через вложенный цикл for. Наш первый цикл for будет перебирать каждый символ в строке A, устанавливая их в качестве первого аргумента в нашем методе split. Вложенный цикл for будет перебирать каждый символ, следующий за символом, выбранным внешним циклом for, и устанавливать их в качестве второго аргумента для нашего метода разделения. Мы сохраним результат нашего разделения в переменной, а затем воспользуемся методом включения строки, чтобы проверить, включает ли строка B эту подстроку строки A. Если строка B включает подстроку, мы добавим эту подстроку в наш выходной массив.
function matchingSubStrings(a, b) { const strA = a.toLowerCase() const strB = b.toLowerCase() let output = [] for(let start = 0; start < strA.length; start++){ for(let end = (start + 1); end <= strA.length; end++){ let segment = strA.slice(start, end) if (strB.includes(segment)) output.push(segment) } } }
Мы почти закончили, теперь нам просто нужно настроить возврат. Помните, что мы должны вернуть false, если совпадений нет.
function matchingSubStrings(a, b) { const strA = a.toLowerCase() const strB = b.toLowerCase() let output = [] for(let start = 0; start < strA.length; start++){ for(let end = (start + 1); end <= strA.length; end++){ let segment = strA.slice(start, end) if (strB.includes(segment)) output.push(segment) } } if (output.length === 0) output = false return output }
И вот, наша функция вернет массив всех совпадающих подстрок между нашими двумя входными строками, возвращая false, если совпадений не существует.