JavaScript 算法 : find starting and ending indices of consecutively repeated chars from a string

Question

我想运行一个函数来执行此操作:

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

Answer 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 },
]