Блог

Главная - Вопросы по программированию - Алгоритмы JavaScript: поиск начальных и конечных индексов последовательно повторяющихся символов из строки

Алгоритмы JavaScript: поиск начальных и конечных индексов последовательно повторяющихся символов из строки

#javascript #algorithm

#javascript #алгоритм

Вопрос:

Я хотел использовать функцию, которая делает это:

 const input =“hellooooloo”;
const results = getRepeated(input);
console.log(results) // [(2,3), (4,7), (9,10)]

Он возвращает массив массивов индексов начального и конечного индексов последовательно повторяющихся символов из строки.

Вот моя попытка, это O(n ^ 2). Интересно, есть ли более элегантный и эффективный способ достижения этой цели

 const input = 'hellooooloo'; 
const results = getRepeated(input); // // [(2,3), (4,7), (9,10)]

function getRepeated(string) {
    const results = []
    if(string.length < 2) return results
    for(let i = 0; i < string.length - 1; i  ) {
        if(i > 1 amp;amp; string[i] === string[i-1]) {
            continue
        }
        let startIndex = i
        let endIndex = i
        for(let j = i   1; j < string.length; j  ) {
            if(string[i] === string[j]) {
                endIndex = j
            } else {
                break
            }
        }
        if(startIndex !== endIndex) {
            results.push([startIndex, endIndex])
        }
    }

    return results
}

Комментарии:

1. Ваш алгоритм не O(n^2) является, он есть O(n) . (Ну, на самом деле, это и то, и другое.) Это происходит из-за логики if … then continue, которая у вас есть в строках 8 и 9. Внутренний цикл (цикл j) выполняет итерацию не более, чем для O(n) шагов в целом. Потому что, если цикл j продолжается, скажем, на m шагов, то для следующих m шагов внешний цикл примет ветвь continue в строке 9.

Ответ №1:

Я бы использовал регулярное выражение: сопоставьте и захватите один символ, затем сделайте обратную ссылку на тот же символ столько раз, сколько сможете. Выполните глобальное сопоставление регулярных выражений со строкой. Возьмите все совпадения и сопоставьте их с массивом их индекса и их индексом плюс длина совпадения:

 const getRepeated = str => [...str.matchAll(/(.)1 /g)]
  .map(({ index, 0: match }) => [index, index   match.length - 1]);

const input = "hellooooloo";
const results = getRepeated(input);
console.log(results) // [(2,3), (4,7), (9,10)]

Это O(n) .

Регулярное выражение означает:

  • (.) — Сопоставьте любой символ, поместите его в группу захвата
  • 1 — Повторите один и тот же символ, соответствующий этой группе захвата, один или несколько раз

Например, для приведенного здесь примера ввода вы получите следующие совпадения:

 [
  { 0: 'll', 1: 'l', index: 2 },
  { 0: 'oooo', 1: 'o', index: 4 },
  { 0: 'oo', 1: 'o', index: 9 },
]

Ответ №2:

Вы могли бы выделить массив символов и проверить, равен ли последний символ фактическому, и скорректировать второй индекс последней пары индексов.

В противном случае проверьте, равен ли фактический символ следующему символу, и создайте новый результирующий набор.

 const
    getRepeated = ([...array]) => array.reduce((r, c, i, a) => {
        if (a[i - 1] === c) r[r.length - 1][1] = i;
        else if (c === a[i   1]) r.push([i]);
        return r;
    }, []),
    input = 'hellooooloo',
    result = getRepeated(input); // [[2, 3], [4, 7], [9, 10]]

console.log(result); 
 .as-console-wrapper { max-height: 100% !important; top: 0; }