942. 增减字符串匹配

942. 增减字符串匹配

leetcode 链接

解法一：遍历 + 交换元素

1、生成 [0, 1, 2, 3... n] 数组 perm。

2、遍历 s 如果 s[i] === 'D' ，那么交换 perm[i] 和 perm[i + 1] 的值，然后如果 s[i - 1] 的值也为 'D'，那么要交换 perm[i - 1] 和 perm[i]，一直往前找，知道 s[j] === 'I'。

/**
 * @param {string} s
 * @return {number[]}
 */
function diStringMatch(s) {
  const perm = Array.from({ length: s.length + 1 }).fill(0).map((item, index) => index)
  for (let i = 0; i < s.length; i++) {
    let j = i
    while (s[j] === 'D' && j >= 0) {
      swap(perm, j, j + 1)
      j--
    }
  }
  return perm
}

function swap(list, index1, index2) {
  const tmp = list[index1]
  list[index1] = list[index2]
  list[index2] = tmp
}

解法二：遍历 + 批量处理

和解法一相似，但是不是挨个交换元素，而是遇到连续的 D之后，将 perm 中这一段元素翻转过来。

/**
 * @param {string} s
 * @return {number[]}
 */
function diStringMatch(s) {
  const perm = Array.from({ length: s.length + 1 }).fill(0).map((item, index) => index)
  for (let i = 0; i < s.length; i++) {
    if (s[i] === 'D') {
      let j = i
      while (s[j] === 'D') {
        j++
      }
      const tmp = perm.slice(i, j + 1).reverse()
      perm.splice(i, j - i + 1, ...tmp)
      i = j
    }
  }
  return perm
}

解法三：贪心

官方解法

function diStringMatch(s) {
  const n = s.length
  let lo = 0
  let hi = n
  const perm = new Array(n + 1).fill(0)
  for (let i = 0; i < n; ++i) {
    perm[i] = s[i] === 'I' ? lo++ : hi--
  }
  perm[n] = lo // 最后剩下一个数，此时 lo == hi
  return perm
}