JavaScript算法:从字符串中查找连续重复的字符的开始和结束索引 [英] JavaScript algorithms: find starting and ending indices of consecutively repeated chars from a string

问题描述

我想运行一个执行此操作的功能:

I wanted to function a function that does this:

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

它从字符串中返回连续重复的char的起始索引和结束索引的索引数组.

It returns an array of arrays of indices of the starting and ending index of consecutively repeated chars from a string.

这是我的尝试，它是O(n ^ 2).我想知道是否有一种更优雅，更有效的方法来实现这一目标

Here is my attempt, it is a O(n^2). I wonder if there is a more elegant and efficient way of achieving this

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 && 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
}

推荐答案

我将使用正则表达式:匹配并捕获一个字符，然后尽可能多地反向引用相同的字符.对字符串执行全局正则表达式匹配.取得所有匹配项并将它们映射到它们的索引数组，以及它们的索引加上匹配项的长度:

I'd use a regular expression: match and capture one character, then backreference that same character as many times as you can. Perform a global regex match on the string. Take all the matches and map them to an array of their index, and their index plus the length of the match:

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 + -重复一次与该捕获组匹配的相同字符

• (.) - Match any character, put it in a capture group
• \1+ - Repeat the same character matched by that capture group one or more times

例如，对于此处输入的示例，您将获得以下匹配项:

Eg, for the example input here, you'll get the following matches:

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

这篇关于JavaScript算法:从字符串中查找连续重复的字符的开始和结束索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！