JavaScript | Алгоритм нахождения одинаковой начальной последовательности символов в массиве из строк — efim360.ru

JavaScript | Алгоритм нахождения одинаковой начальной последовательности символов в массиве из строк

Нам нужно найти такую строку (часть строки), которая присутствует во всех элементах массива и с которой начинаются все элементы массива. Как решить такую задачу?

Предлагаю посмотреть на данные, с которыми хотим работать:

  1. https://a.ru/q
  2. https://a.ru/d
  3. https://a.ru/f
  4. https://a.ru/g
  5. https://a.ru/h/k

Этот пример простой и тут всё и так очевидно. Мы напишем свою функцию. Решение задачи состоит из нескольких этапов.

 

Шаг № 1 - Все ли строки начинаются на одно и тоже?

Этот этап опциональный. Он нужен для понимания задачи.

На самом первом этапе предлагаю получить все первые символы строк и сравнить их на уникальность. Если они все равны, то можно пытаться идти дальше. Если хотя бы один символ выбивается из общей массы первых символов, то это значит, что они не одинаковые - значит строки не начинаются на одинаковую последовательность.

let arr =['https://a.ru/q', 'https://a.ru/d', 'https://a.ru/f', 'https://a.ru/g', 'https://a.ru/h/k'];

Я перевёл наши данные в массив и теперь буду работать с ним.

arr.map(i=>i[0]);
new Set(arr.map(i=>i[0]));
(new Set(arr.map(i=>i[0]))).size;
Получили размер Набора равный 1 в JavaScript
Получили размер Набора равный 1 в JavaScript

На выходе получаем единицу. Именно она нам и говорит о том, что в наборе из первых символов всех строк массива находятся одинаковые символы.

Условие будет выглядеть так:

(new Set(arr.map(i=>i[0]))).size===1;

Если оно истинно, тогда двигаемся дальше.

 

Шаг № 2 - Функция сравнения массива из одинарных символов

По сути нам нужно повторять первую ситуацию до тех пор, пока не вернётся false.

function isSetOne(array){return (new Set(array)).size===1};

или

let isSetOne = (array) => (new Set(array)).size===1;

Для теста:

isSetOne(['d', 'd', 'd', 'd'])
isSetOne(['d', 'r', 'd', 't'])
Функция проверки что Набор состоит из одного значения - JavaScript
Функция проверки что Набор состоит из одного значения - JavaScript

Эта функция всегда будет получать массив из строк, которые содержат всего один символ. Возвращать она будет ИСТИНУ или ЛОЖЬ.

Если элементы одинаковы, значит ИСТИНА, во всех остальных случаях ЛОЖЬ.

Место строки в котором посимвольное сравнение слева-направо состоит не из одного символа
Место строки в котором посимвольное сравнение слева-направо состоит не из одного символа

 

Шаг № 3 - Функция конкатенатор одиночных Наборов

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

function concatTrueSets(mainarray){

    for(let x = '', tik=0; ; tik++){

        if(

            isSetOne(mainarray.map(i=>i[tik]))

        ){

            x+=mainarray[0][tik]

        }

        else{

            return x

        }

    }

};

 

Мы передаём в функцию весь наш оригинальный массив из строк. По нему будут отрезаться позиции символов каждой строки. Он нужен для выбирания Наборов одиночных символов. Выборкой занимается метод map().

За движение слева направо отвечает переменная tik. Она осуществляет сдвиг Наборов.

Переменная x накапливает одиночные символы из каждого ТРУШНОГО НАБОРА по сдвигу.

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

Эта последовательность и будет нашей одинаковой начальной последовательностью по всем строкам оригинального массива.

 

Шаг № 4 - Ограничение работы цикла

Нашему циклу не хватает остановки. Это может привести к зависанию. В какой момент нужно прекращать сопоставлять строки и Наборы?

По сути нам нужно найти длину самой короткой строки. Напишем для этого отдельную функцию:

// Получение длины самой короткой строки

function getShortStrLength(arrofstr){

    return arrofstr.map(i=>i.length).sort((a,b)=>a-b)[0]

}

// Функция в одну строку

function getShortStrLength(arrofstr){return arrofstr.map(i=>i.length).sort((a,b)=>a-b)[0]}

 

Шаг № 5 - Итоговая функция

function same_initial_sequence_of_characters(mainarray){

    for(let x = '', l = mainarray.map(i=>i.length).sort((a,b)=>a-b)[0], tik=0; tik < l; tik++){

        if(isSetOne(mainarray.map(i=>i[tik])))

        {x+=mainarray[0][tik]}

        else

        {return x}

    }

}

 

Если мы её выполним на нашем массиве, то получим

same_initial_sequence_of_characters(arr)
'https://a.ru/'

 

Тестовые вызовы

same_initial_sequence_of_characters(['куар','куан','куащ','куадпрпр'])
'куа'
same_initial_sequence_of_characters(['11','12','13','14'])
'1'
same_initial_sequence_of_characters(['0','1','3','4'])
''
same_initial_sequence_of_characters(['','','',''])
undefined
Функция нахождения одинаковой начальной последовательности символов в массиве из строк - JavaScript
Функция нахождения одинаковой начальной последовательности символов в массиве из строк - JavaScript

 

Информационные ссылки

Стандарт ECMAScript - https://tc39.es/ecma262/multipage/