今天的題單：

• Roman to Integer

• Backspace String Compare

13. Roman to Integer

思路：羅馬數字大原則還是從左到右累加，只有 I、X、C 遇到後面有接字母才會變成減法。因此用 linear scan 過去遇到這三這數字的時候看一下後面有沒有接字母就可以決定要加還是減。

• 題目的 input 是 valid roman number，不用考慮 unvalid case

• 數字不會大於 3999，所以總和用 int 即可

class Solution {
public:
    int romanToInt(string s) {
        int num = 0;

        unordered_map<char, int> roman_number;
        roman_number['I'] = 1;
        roman_number['V'] = 5;
        roman_number['X'] = 10;
        roman_number['L'] = 50;
        roman_number['C'] = 100;
        roman_number['D'] = 500;
        roman_number['M'] = 1000;
        

        for (int i = 0; i < s.size(); i++) {
            char next;
            if (i + 1 < s.size()) {
                next = s[i + 1];
            }
            
            if (s[i] == 'I') {
                if (next == 'V' || next == 'X') {
                    num -= roman_number[s[i]];
                } else {
                    num += roman_number[s[i]];
                }
            } else if (s[i] == 'X') {
                if (next == 'L' || next == 'C') {
                    num -= roman_number[s[i]];
                } else {
                    num += roman_number[s[i]];
                }
            } else if (s[i] == 'C') {
                if (next == 'D' || next == 'M') {
                    num -= roman_number[s[i]];
                } else {
                    num += roman_number[s[i]];
                }
            } else {
                num += roman_number[s[i]];
            }
        }
        return num;
    }
};

844. Backspace String Compare

思路：直接按照 string 操作，最後比較兩個 string 是否一樣。（O(n) time, O(n) space）

• 我用 string 存操作結果，也可以用 stack

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        string typeS = "";
        string typeT = "";

        for (char c : s) {
            if (c == '#') {
                if (!typeS.empty()) {
                    // remove the last character
                    typeS.pop_back();
                }
            } else {
                typeS.push_back(c);
            }
        }

        for (char c : t) {
            if (c == '#') {
                if (!typeT.empty()) {
                    // remove the last character
                    typeT.pop_back();
                }
            } else {
                typeT.push_back(c);
            }
        }

        if (typeS == typeT) {
            return true;
        } else {
            return false;
        }
    }
};

Follow up: Can you solve it in O(n) time and O(1) space?

思路：要求 O(1) space，不能另外建立 string 或 stack 儲存結果。一樣是模擬，不過這次是從 string 尾端操作。不過我不想要直接操作 input。

• 使用 two pointer 方法，分別指向 string 尾端往前 scan

• 一旦跳過 # 和被刪掉的字符就停下來，比較指到的 non-# 字符

參照了 Leetcode sample code，另外在網路上有看到作法相同但是直接操作 input string 的方法，與之相比這個方法的優點是不需要 erase 產生額外 cost。

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int count_S = 0;
        int count_T = 0;
        int s_idx = s.length() - 1;
        int t_idx = t.length() - 1;

        while (true) {
            // scan the string from back
            // skip the charactor which needs to be moved 
            while (s_idx >= 0) {
                if (s[s_idx] == '#') {
                    count_S++;
                } else {
                    if (count_S > 0) {
                        count_S--;
                    } else {
                        break;
                    }
                }
                s_idx--;
            }

            while (t_idx >= 0) {
                if (t[t_idx] == '#') {
                    count_T++;
                } else {
                    if (count_T > 0) {
                        count_T--;
                    } else {
                        break;
                    }
                }
                t_idx--;
            }

            if (s_idx < 0 || t_idx < 0) {
                break;
            }
            
            // If the characters at the stopping point are not the same, 
            // the results will not be the same at the end.
            if (s[s_idx] != t[t_idx]) {
                return false;
            }

            s_idx--;
            t_idx--;
        }
        // if there are charactor (not '#') left, it means the results are not same.
        if (s_idx == -1 && t_idx == -1) {
            return true;
        } else {
            return false;
        }
    }

};