[LeetCode] 會把阿拉伯數字轉羅馬，你也轉得回來 #13 Roman to Integer

阿拉伯數字 -> 羅馬數字

回顧一下 LeetCode #12，我們觀察羅馬數字一定是從大排到小:

如果要轉回數字，我們按照顏色的區塊也是從大到小轉回來就好了。

要小心的陷阱

這題目其實一點都不 Easy，如果你從左到右讀字串，最容易遇到的問題就是:

如果你讀到一個字元 "I" 就很開心的以為這是 1，但其實他只是 "IV" = 4 的一部分怎麼辦?

所以大部分解答都花了很多力氣去處理這類的問題，看了 code 就會覺得很頭痛。

轉換的順序

Step    Symbol    Value
1       M         1000
2       CM        900
3       D         500
4       CD        400
5       C         100
6       XC        90
7       L         50
8       XL        40
9       X         10
10      IX        9
11      V         5
12      IV        4
13      I         1

如果我們按照上面這樣 Step 1~13 看 string 前面長的一樣就加上數字，不一樣就去下一個 step，永不回頭，會有什麼問題嗎?

前面我們說可能會搞混的像是 IV=4 和 I=1，可是 Step 12 先判斷最不合群的 "IV" = 4，失敗了 Step 13 再去判斷是不是 "I" = 1 或 "II" = 2 或 "III" = 3，就不可能會搞混 1~4 的數字。

其他更大的數字也是如此，你可以抓兩個容易搞混的羅馬數字試試看。

C++ Code

我們就按照 Step 1~13 慢慢判斷，程式碼就會長得像這樣:

struct RomanAndValue {
  std::string romanStr;
  int value = 0;
};

class Solution {
 public:
  int romanToInt(std::string s) {
    static const RomanAndValue TABLE[] = {
        {"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100},
        {"XC", 90},  {"L", 50},   {"XL", 40}, {"X", 10},   {"IX", 9},
        {"V", 5},    {"IV", 4},   {"I", 1},
    };

    int num = 0;
    for (const auto &item : TABLE) {
      while (s.substr(0, item.romanStr.length()) == item.romanStr) {
        num += item.value;
        s = s.substr(item.romanStr.length());
      }
    }
    return num;
  }
};

要用別的程式語言來做我相信也是非常容易。

萬用解法

上面這個解法其實和 LeetCode #12 的解法非常類似，我們來回顧一下:

struct RomanAndValue {
  std::string romanStr;
  int value = 0;
};

class Solution {
 public:
  std::string intToRoman(int num) {
    static const RomanAndValue TABLE[] = {
        {"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100},
        {"XC", 90},  {"L", 50},   {"XL", 40}, {"X", 10},   {"IX", 9},
        {"V", 5},    {"IV", 4},   {"I", 1},
    };

    std::string roman;
    for (const auto &item : TABLE) {
      while (num >= item.value) {
        roman += item.romanStr;
        num -= item.value;
      }
    }
    return roman;
  }
};

那我們可不可以把兩個解法合起來，變成 #12 #13 題都可以解?

把一模一樣的 TABLE 拿到外面去之後:

struct RomanAndValue {
  std::string romanStr;
  int value = 0;
};

static const RomanAndValue TABLE[] = {
    {"M", 1000}, {"CM", 900}, {"D", 500}, {"CD", 400}, {"C", 100},
    {"XC", 90},  {"L", 50},   {"XL", 40}, {"X", 10},   {"IX", 9},
    {"V", 5},    {"IV", 4},   {"I", 1},
};

class Solution {
 public:
  std::string intToRoman(int num) {
    std::string roman;
    for (const auto &item : TABLE) {
      while (num >= item.value) {
        roman += item.romanStr;
        num -= item.value;
      }
    }
    return roman;
  }

  int romanToInt(std::string s) {
    int num = 0;
    for (const auto &item : TABLE) {
      while (s.substr(0, item.romanStr.length()) == item.romanStr) {
        num += item.value;
        s = s.substr(item.romanStr.length());
      }
    }
    return num;
  }
};

這程式碼拿去丟 #12 或 #13 結果都會過。

哇，我們真的是超偷懶的。

Submission 結果

這題速度和記憶體都不是關鍵，了解羅馬數字的閱讀方法之後，寫出最 clean 的程式碼才是我們想要的。