Clean O(n) c++ solution


  • 79
    W

    Problem is simpler to solve by working the string from back to front and using a map. Runtime speed is 88 ms.

    int romanToInt(string s) 
    {
        unordered_map<char, int> T = { { 'I' , 1 },
                                       { 'V' , 5 },
                                       { 'X' , 10 },
                                       { 'L' , 50 },
                                       { 'C' , 100 },
                                       { 'D' , 500 },
                                       { 'M' , 1000 } };
                                       
       int sum = T[s.back()];
       for (int i = s.length() - 2; i >= 0; --i) 
       {
           if (T[s[i]] < T[s[i + 1]])
           {
               sum -= T[s[i]];
           }
           else
           {
               sum += T[s[i]];
           }
       }
       
       return sum;
    }

  • 1
    Q

    woo, It's my idea. but I can't do that so simplely. sorry for my English.


  • 13
    W

    Clean indeed. But maybe You'd better check if the string is empty before use s.back().
    I use vector instead of unordered_map for better performance (36ms):

    int romanToInt(string s) {
        if (s.empty()) return 0;
        
        int roman[24] = {};
        roman['I' - 'A'] = 1;
        roman['V' - 'A'] = 5;
        roman['X' - 'A'] = 10;
        roman['L' - 'A'] = 50;
        roman['C' - 'A'] = 100;
        roman['D' - 'A'] = 500;
        roman['M' - 'A'] = 1000;
        
        auto sum = 0;
        auto right = roman[s.front() - 'A'];
        for (int i = 1; i < s.size(); ++i) {
            auto curr = right;
            right = roman[s[i] - 'A'];
            if (right > curr) 
                sum -= curr;
            else 
                sum += curr;
        }
        
        return sum + right;
    }

  • 1

    I just love ternary expression >_<

    class Solution {
    public:
        int romanToInt(string s) {
            unordered_map<char, int> T = { { 'I' , 1 }, { 'V' , 5 }, { 'X' , 10 }, { 'L' , 50 }, { 'C' , 100 }, { 'D' , 500 }, { 'M' , 1000 } };
            int sum = T[s.back()];
            for(int i = s.length() - 2; i >= 0; --i){
                sum +=  (T[s[i]] < T[s[i+1]] ? -T[s[i]] : T[s[i]]);
            }
            return sum;
        }
    };
    

  • 3
    T

    My idea is same as yours too. there's no need to use map here it will be slower. Array is much more better see @wfxr answer
    the following code runs in 20ms

    int roman(char c) {
        switch(c) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }
    
    int romanToInt(char* s) {
        int sum = 0;
        while(*s) {
            int cur = roman(s[0]), next = roman(s[1]);
            if(cur<next)
                sum+=-cur;
            else
                sum+=cur;
            s++;
        }
        return sum;
    }
    

  • 0
    M

    Great syntactic analysis. If we take care of that one special case, then front to back also works. Here is the C code.

    int romanToInt(char* s)
    {
        /*            C    D    E, F, G, H, I, J, K, L      M, N,  O, P */
        int nv[22] = {100, 500, 0, 0, 0, 0, 1, 0, 0, 50, 1000, 0,  0, 0,
        /*            Q,   R    S,  T,  U,  V,  W,  X  */
                      0,   0,   0,  0,  0,  5,  0,  10};
        int num = 0, i;
    
        /* Loop and process all the characters */
        for (i = 0; s[i]; ++i)
            num += (s[i + 1] && nv[CH_OFF(s[i])] < nv[CH_OFF(s[i + 1])]) ?
                    -nv[CH_OFF(s[i])] : nv[CH_OFF(s[i])];
    
        /* Return the number */
        return num;
    }
    ``

  • 2
    K

    This solution is not complete. For instance, VL is parsed as 45 but it's actually a wrong roman numeral. Ramon numeral of 45 is XLV


  • 0
    W

    @kwrush

    That's an astute observation. Interestingly, some online Roman numeral converters are incorrectly saying that VL and XLV are both 45, so they are incomplete as well. But according to wikipedia there's rules to the subtractive property where 'V', 'L' and 'D' can never be subtracted.

    I don't remember the problem statement clarifying this property. Hence, I think this entire question needs to be clarified and tests updated to reflect this property. It does make the problem a little more complex, which is probably why it was omitted originally.


  • 0
    T

    @kwrush
    I don't consider the solution incomplete. In practical, we usually assume input is correct to gain speed. The critical section need to be as simple as possible. While the correctness could be externally promised. See the example below. An GCD function.

    // assume a is always greater than b
    int gcd(int a, int b) {
      if(b==0) return a;
      // b >= a%b
      return gcd(b, a%b);
    }
    

    Without the assumption, we might need to check and swap many times. Which can be a lot slower when the critical section runs millions of times.

    The test data will never contain illegal input, by the time it says input is a roman numeric. It promised the correctness.


  • 0
    I
    This post is deleted!

  • 0
    J

    @tim37021 Looks gorgeous though it might be unfair to compare performance between C and CppšŸ˜‚


  • 0
    T

    @jessehui
    It is always possible to make c++ as fast as c. it takes unordered_map O(n) to locate the entry. why not using pure array or vector?


  • 0
    L

    adorableļ¼ this is simpler than mine more and more!


  • 0
    M

    @wfxr
    Furthermore, I think we should add a check for invalid characters in the for loop before accessing the roman array. Otherwise, segfault might occur when the input contains characters other than "IVXLCDM".

    Like

    if (UNLIKELY(s[i] != 'I' && s[i] != 'V' && s[i] != 'X' && s[i] != 'L' && s[i] != 'C' && s[i] != 'D' && s[i] != 'M')) {
        throw runtime_error("Invalid character");
    }
    

  • 0
    S

    @wfxr map is so useful and so strong that beats my if...else...or switch!


  • 0
    Z

    Map makes the code much simpler and more readable. BTW, It can be solved from the beginning.

    int romanToInt(string s) {
            if (s.empty()) return 0;
            
            unordered_map<char, int> table = {
                {'I', 1},
                {'V', 5},
                {'X', 10},
                {'L', 50},
                {'C', 100},
                {'D', 500},
                {'M', 1000}
            };
            int num = 0;
            for (int i = 0; i < s.length() - 1; ++i) {
                if (table[s[i]] < table[s[i + 1]]) {
                    num -= table[s[i]];
                } else {
                    num += table[s[i]];
                }
            }
            num += table[s.back()];
    
            return num;
        }
    

  • 0
    J

    @kwrush I also think so, so my solution is:
    for (int i = s.length()-2; i>=0; i--)
    {
    int tmp = cti[s[i+1]]/cti[s[i]];
    if( tmp == 5 || tmp == 10)
    {
    num -= cti[s[i]];
    }
    else
    num += cti[s[i]];
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.