13. Roman to Integer

題目 / Problem

中文： 羅馬數字由七個符號表示：I(1)、V(5)、X(10)、L(50)、C(100)、D(500)、M(1000)。

通常羅馬數字從大到小、由左到右書寫，例如 XII = 12、XXVII = 27。但有六種「減法」特例：

• I 放在 V 或 X 前面 → 4 (IV)、9 (IX)
• X 放在 L 或 C 前面 → 40 (XL)、90 (XC)
• C 放在 D 或 M 前面 → 400 (CD)、900 (CM)

給定一個合法的羅馬數字字串，將它轉成整數。

English: Roman numerals use seven symbols I/V/X/L/C/D/M. They are normally written largest-to-smallest, left-to-right (so XII = 12). There are six subtractive pairs where a smaller numeral precedes a larger one to mean "subtract": IV=4, IX=9, XL=40, XC=90, CD=400, CM=900. Given a valid Roman numeral string, return its integer value.

Constraints: - 1 <= s.length <= 15 - s contains only I, V, X, L, C, D, M - s is guaranteed valid, with value in [1, 3999]

Worked example: s = "MCMXCIV" → M(1000) + CM(900) + XC(90) + IV(4) = 1994.

名詞解釋 / Glossary

• 羅馬數字 / Roman numeral: 一種古代計數系統，用字母表示固定的數值。例如 M 永遠等於 1000。A counting system where each letter has a fixed value (e.g. M is always 1000).
• 減法配對 / Subtractive pair: 當一個較小的符號出現在較大的符號 左邊，這對符號代表「大減小」(例如 IV = 5 - 1 = 4)。When a smaller symbol appears immediately before a larger one, the pair means "larger minus smaller".
• 查找表 / Lookup table: 一個把鍵 (key) 對應到值 (value) 的資料結構。這裡用來把字元 'I'/'V'/.../'M' 轉成數字。A data structure mapping keys to values; here we map a character to its numeric value.
• 雜湊表 / Hash map (unordered_map): C++ STL 中的查找表，平均 O(1) 取值。C++ STL container providing average O(1) key-to-value lookup.
• switch 敘述 / switch statement: C/C++ 用來依據變數值選擇不同分支的語法，效果類似一連串 if/else。Selects a code branch based on a value — like a chain of if/else but more compact.
• 單次掃描 / Single pass: 從頭到尾只看每個字元一次，時間複雜度 O(n)。Visit each character once, giving O(n) time.

思路

中文：最直觀的暴力方法是先掃一次字串，找出所有可能的「減法配對」(IV/IX/XL/XC/CD/CM)，然後再把剩下的字元加總。這當然可行，但需要寫六個特例判斷，容易漏掉。我們可以用一個更簡潔的觀察：羅馬數字「正常」狀況下是從大到小排列，所以一個字元如果比它 右邊 的字元小，它就應該被「減掉」而不是「加上」。例如 IV 裡的 I 因為比右邊的 V 小，所以貢獻 -1 而不是 +1。基於這個規則，我們只要從左到右掃一次字串，比較每個字元和「下一個字元」的數值大小：若 value[s[i]] < value[s[i+1]]，就減去；否則就加上。最後一個字元沒有右鄰，永遠是加。整個演算法只需要一個查找表 (七個常數) 加上一輪線性掃描，時間 O(n)、空間 O(1)。提示建議「從後往前」也可以，本質上是等價的；這裡選擇前往後比較容易跟一般人讀字串的方向一致。

English: The brute-force approach is to scan the string and explicitly detect each of the six subtractive pairs (IV/IX/XL/XC/CD/CM), then sum what's left. That works but is bug-prone — six special cases is easy to mess up. A cleaner observation: Roman numerals are normally written large-to-small, so any symbol whose value is smaller than the symbol on its right must be a subtractive prefix. For instance, in IV the I is smaller than the V to its right, so it contributes -1 instead of +1. With this rule we make one left-to-right pass: for each position i, if value[s[i]] < value[s[i+1]] subtract it, otherwise add it. The last character has no right neighbor, so it is always added. We only need a 7-entry lookup table and one linear scan — O(n) time, O(1) space. (The hint suggests right-to-left; that is equivalent — comparing to the previous maximum-so-far. Left-to-right is just as clean.)

逐步走查 / Walkthrough

Trace s = "MCMXCIV" (expected output 1994). total starts at 0.

最後 total = 1994，與預期相符 / matches the expected answer.

Solution — C

// 演算法 / Algorithm:
//   單次線性掃描。對每個字元，若其數值小於右鄰則減去，否則加上;
//   末字元永遠加。利用 switch 當查找表，常數空間。
//   Single linear pass: subtract a symbol if it's smaller than its right
//   neighbor, otherwise add it; the last symbol is always added.
//   A switch acts as the lookup table — constant space.

// 把單一羅馬字母轉成整數值 / Convert one Roman letter to its integer value.
static int val(char c) {
    // switch 依字元跳到對應分支 / switch jumps to the matching branch.
    switch (c) {
        case 'I': return 1;     // I = 1
        case 'V': return 5;     // V = 5
        case 'X': return 10;    // X = 10
        case 'L': return 50;    // L = 50
        case 'C': return 100;   // C = 100
        case 'D': return 500;   // D = 500
        case 'M': return 1000;  // M = 1000
        default:  return 0;     // 題目保證合法,理論上走不到 / unreachable by constraint
    }
}

int romanToInt(char* s) {
    int total = 0;              // 累積答案 / running total
    // 用標準函式 strlen 取得字串長度;LeetCode C 環境已包含 <string.h>
    // Use strlen() to get the length; <string.h> is included by LeetCode's harness.
    int n = (int)strlen(s);

    // 從第 0 個字元掃到最後一個 (索引 n-1) / iterate from index 0 to n-1.
    for (int i = 0; i < n; i++) {
        int cur = val(s[i]);    // 當前字元的數值 / value of current symbol

        // 若還有右鄰,且當前比右鄰小 → 減法配對的左邊一半
        // If there is a right neighbor and current < neighbor, this is a subtractive prefix.
        if (i + 1 < n && cur < val(s[i + 1])) {
            total -= cur;       // 減去當前值 / subtract it
        } else {
            total += cur;       // 否則加上 (含最後一個字元) / otherwise add (also covers last char)
        }
    }

    return total;               // 回傳結果 / return the accumulated value
}

Solution — C++

// 演算法 / Algorithm:
//   與 C 版相同 — 線性掃描,若當前符號小於右鄰則減,否則加。
//   差別:用 unordered_map<char,int> 當查找表,寫法更貼近現代 C++。
//   Same algorithm as the C version — linear scan, subtract when current
//   symbol is smaller than its right neighbor, otherwise add.
//   Implementation uses unordered_map<char,int> for an idiomatic C++ lookup.

#include <string>
#include <unordered_map>

class Solution {
public:
    int romanToInt(std::string s) {
        // unordered_map 是 STL 雜湊表,鍵→值平均 O(1) 查找
        // unordered_map is the STL hash map — average O(1) lookup by key.
        // 用 static const 避免每次呼叫都重建這張表 / static const avoids rebuilding the table per call.
        static const std::unordered_map<char, int> value = {
            {'I', 1},    {'V', 5},    {'X', 10},   {'L', 50},
            {'C', 100},  {'D', 500},  {'M', 1000},
        };

        int total = 0;                       // 累積答案 / running total
        int n = static_cast<int>(s.size());  // 字串長度 / string length

        // 從左到右逐字元處理 / process each character left to right.
        for (int i = 0; i < n; i++) {
            // .at(key) 回傳對應的值;若鍵不存在會丟例外 (本題保證合法,不會發生)
            // .at(key) returns the mapped value; throws if missing (guaranteed not to happen here).
            int cur = value.at(s[i]);

            // 判斷是否為「減法配對」的左半部:有右鄰且比右鄰小
            // Check the subtractive-pair rule: a right neighbor exists and current < neighbor.
            if (i + 1 < n && cur < value.at(s[i + 1])) {
                total -= cur;                // 減 / subtract
            } else {
                total += cur;                // 加 (包含最後一個字元) / add (also handles last char)
            }
        }

        return total;                        // 結果 / answer
    }
};

複雜度 / Complexity

• Time: O(n) — 我們對長度 n 的字串只掃一次,每步做常數次查找與比較。n 是字串長度 (本題最多 15)。We scan the string once and do O(1) work per character (table lookup + compare). n is the string length (≤ 15 here).
• Space: O(1) — 查找表只有 7 個固定項目,不隨輸入成長;其餘變數 (total, i, cur) 也都是常數。The lookup table has a fixed 7 entries, and we use only a handful of scalar variables — nothing grows with n.

Pitfalls & Edge Cases

• 忘記檢查右鄰是否存在 / Forgetting to bounds-check the right neighbor: 存取 s[i+1] 時必須先確認 i + 1 < n,否則會讀到字串結尾的 '\0' 或越界。程式碼用 if (i + 1 < n && ...) 的短路求值避免這個問題。Always guard s[i+1] with i + 1 < n; the && short-circuits safely.
• 誤把「減法」當特例硬編 / Hard-coding all six subtractive pairs: 容易漏掉一兩種 (例如忘了 CD 或 CM)。比較相鄰大小的規則自動涵蓋全部六種,更不易出錯。Comparing neighbors handles all six pairs uniformly — far less error-prone than enumerating them.
• 方向搞錯 / Direction confusion: 規則是「當前 < 右邊 就減」。如果改成跟左邊比,邏輯就要反過來 (從右往左掃,跟「目前最大值」比較)。兩種方向都對,但不能混。"Smaller than the symbol on the right" — don't mix this with the right-to-left variant, which compares to the running max.
• 溢位 / Overflow: 答案上限 3999,遠在 int 範圍內,無須擔心。Result ≤ 3999, well within int — no overflow risk.
• 空字串 / Empty input: 題目保證 s.length >= 1,但程式邏輯 (迴圈 + total = 0) 對空字串也會正確回傳 0,屬於免費的健壯性。Constraints rule it out, but the loop naturally returns 0 for an empty string anyway.