Simple C++ 8 lines O(n) solution


  • 0
     int romanToInt(string s) {
            // Rule:
            // 'I'= 1, 'X' = 10,'C' = 100, 'M' = 1000, 'V' = 5, 'L' = 50, 'D' = 500;
            // Adjacent(Left) >= Adjacent(Right): Right + Left;
            // Adjacent(Left) < Adjacent(Right): Right - Left;
            unordered_map<char,int>m({{'I',1}, {'X',10}, {'C',100}, {'M',1000}, {'V',5}, {'L',50}, {'D',500}});
            if(s.size()==0) return 0;
            string::iterator r=s.end()-1;
            string::iterator l=r-1;
            int sum=m[*r];
            while(r-s.begin()>=0){
               if(m[*r]<=m[*l]) sum+=m[*l];
               else sum-=m[*l];
               l--;
               r--;
            }
            return sum;
        }
    

    Update(08/13/2017):

        int romanToInt(string s) {
            // Rule:
            // 'I'= 1, 'X' = 10,'C' = 100, 'M' = 1000, 'V' = 5, 'L' = 50, 'D' = 500;
            // Adjacent(Left) >= Adjacent(Right): Right + Left;
            // Adjacent(Left) < Adjacent(Right): Right - Left;
            unordered_map<char,int>m({{'I',1}, {'X',10}, {'C',100}, {'M',1000}, {'V',5}, {'L',50}, {'D',500}});
            if(s.size() == 0) return 0;
            int sum = m[s[s.size() - 1]];
            for(int i = s.size() - 2; i >= 0; i--){
                if(m[s[i]] >= m[s[i + 1]]) sum += m[s[i]];
                else sum -= m[s[i]];
            }
            return sum;
        }
    

Log in to reply
 

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