JavaScript LeetCode 13. Roman to Integer

將羅馬數字轉換為整數，這題目現實中看到可能自己腦袋都要轉一下了，更別說要用程式去拆解，思考了一下寫出了下面這段 code，順便練習一下遞迴了。

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  const map = new Map();
  map.set("I", 1);
  map.set("V", 5);
  map.set("X", 10);
  map.set("L", 50);
  map.set("C", 100);
  map.set("D", 500);
  map.set("M", 1000);
  let sum = 0;
  const arr = s.split("");

  _summarySymbol(arr);

  return sum;

  function _summarySymbol(arr) {
    if (arr.length === 0) {
      return;
    }

    const current = arr[0];
    const next = arr[1];

    if (
      (current === "I" && next === "V") ||
      (current === "I" && next === "X")
    ) {
      sum += map.get(next) - map.get(current);
      arr = arr.slice(2);
    } else if (
      (current === "X" && next === "L") ||
      (current === "X" && next === "C")
    ) {
      sum += map.get(next) - map.get(current);
      arr = arr.slice(2);
    } else if (
      (current === "C" && next === "D") ||
      (current === "C" && next === "M")
    ) {
      sum += map.get(next) - map.get(current);
      arr = arr.slice(2);
    } else {
      sum += map.get(current);
      arr = arr.slice(1);
    }

    _summarySymbol(arr);
  }
};

跑是跑過了，效能很差，時間跟空間複雜度也很糟糕，簡單來說就是暴力解

這又是我第二個解法，比前面一個硬幹好多了，其實後來想想也就是如果 n < n+1 那就減去 n
所以如果說 IV 可以拆解成 -1 + 5 = 4
又或者 MCM 可以拆解成 1000 - 100 + 1000 = 1900 如此一來邏輯就通順了，於是可以改成下面這樣

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function (s) {
  const map = new Map();
  map.set("I", 1);
  map.set("V", 5);
  map.set("X", 10);
  map.set("L", 50);
  map.set("C", 100);
  map.set("D", 500);
  map.set("M", 1000);
  let sum = 0;
  const arr = s.split("");
  for (let i = 0; i < arr.length; i++) {
    const current = map.get(arr[i]);
    const next = map.get(arr[i + 1]);

    if (next && current < next) {
      sum -= current;
    } else {
      sum += current;
    }
  }
  return sum;
};

怎麼還有 50% 的人運行速度比我還快啊。