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[]}
 */
var diStringMatch = function (s) {
  const perm = new Array(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[]}
 */
var diStringMatch = function (s) {
  const perm = new Array(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;
};

解法三：贪心

官方解法

var diStringMatch = function (s) {
  let n = s.length,
    lo = 0,
    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;
};