JavaScript如何查找字符串中所有子串的起止索引

实现思路 #

• 第一步：遍历所有目标子串，循环调用indexOf查找每个子串的所有匹配位置，解决单次匹配的问题
• 第二步：对所有匹配区间按起始位置排序，合并重叠区间，满足重叠子串统一包裹的需求

完整实现代码 #

function findOccurrances(str, words) {
  // 收集所有匹配区间
  const allIntervals = []
  words.forEach(word => {
    if (word.length === 0) return // 过滤空串避免死循环
    let pos = str.indexOf(word)
    while (pos !== -1) {
      allIntervals.push([pos, pos + word.length])
      // 从下一个位置开始查找下一个匹配
      pos = str.indexOf(word, pos + 1)
    }
  })
  // 合并重叠区间
  if (allIntervals.length === 0) return []
  // 按区间起始位置升序，起始相同则按结束位置降序排序
  allIntervals.sort((a, b) => a[0] - b[0] || b[1] - a[1])
  const merged = [allIntervals[0]]
  for (let i = 1; i < allIntervals.length; i++) {
    const last = merged[merged.length - 1]
    const curr = allIntervals[i]
    // 当前区间和上一个区间重叠则合并，不重叠则直接加入
    if (curr[0] < last[1]) {
      last[1] = Math.max(last[1], curr[1])
    } else {
      merged.push(curr)
    }
  }
  return merged
}

测试验证 #

测试用例1 #

const str = 'aabc'
const target = ['aa', 'bc']
console.log(findOccurrances(str, target)) // 输出 [[0,2], [2,4]] 符合预期

测试用例2 #

const str = 'aabc'
const target = ['a', 'bc']
console.log(findOccurrances(str, target)) // 输出 [[0,1], [1,2], [2,4]] 符合预期

重叠场景测试 #

const str = 'aabc'
const target = ['aa', 'a']
console.log(findOccurrances(str, target)) // 输出 [[0,2]] 符合重叠合并要求

内容的提问来源于stack exchange，提问作者Joji