Categories: JS

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

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

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

(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

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

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

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

 

Шаг № 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

 

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

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

admin

Share
Published by
admin

Recent Posts

PostgreSQL | Как получить первый элемент из ячейки типа record?

При помощи функции "row()" мы можем создавать записи - данные с типом record. -- Создаём…

1 год ago

PostgreSQL | Как отфильтровать JSONB-массив объектов по логическому значению ключа?

-- массив JSONB с объектами select '[{"id":1, "q":true}, {"id":2, "q":false}, {"id":3, "q":true}, {"id":4, "q":false}]'::jsonb; --…

1 год ago

PostgreSQL | Как отбросить нули в типе numeric?

Функция "trim_scale()" умеет отбрасывать лишние нули в числах с типом numeric. select trim_scale(37.000000000); -- 37…

1 год ago

JavaScript | Как получить следующий день?

Следующий день относительно текущего т. е. "завтра" var tomorrow = new Date(); tomorrow.setDate(tomorrow.getDate() + 1);…

1 год ago

PostgreSQL | Агрегация JSONB-объектов в один объект

У нас есть столбец из JSONB объектов. Нам нужно соединить все объекты этого столбца в…

1 год ago

PostgreSQL | Группировка по 10 записей

Не всегда нужно группировать записи таблиц в рамках какого-то повторяющегося значения столбца. Иногда нужно просто…

1 год ago