Roman to Integer
LeetCode #13 · Easy · Math · C++ solution with worked-out approach and complexity analysis.
Approach
Iterative check with lookahead
Iterate through the string. For each character, check if it forms a subtractive pair with the next character (e.g., IV, IX). If so, add the combined value and skip the next char. Otherwise, add the value of the single character.
Time
O(n)
n is the length of the string
Space
O(1)
Problem description(from LeetCode)
Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Given a roman numeral, convert it to an integer.
Examples
Example 1
- Input:
- s = "III"
- Output:
- 3
- Note:
- L = 50, V= 5, III = 3. Input: s = "MCMXCIV" Output: 1994 Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.
Constraints
- •1 <= s.length <= 15
- •s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').
- •It is guaranteed that s is a valid roman numeral in the range [1, 3999].
C++ Solution
solution.cpp
class Solution {
public:
int romanToInt(string s) {
int total = 0;
for (int i = 0; i < s.length(); i++) {
if (i < s.length() - 1) {
int inc = 0;
if (s[i] == 'I' && s[i + 1] == 'V') inc = 4;
else if (s[i] == 'I' && s[i + 1] == 'X') inc = 9;
else if (s[i] == 'X' && s[i + 1] == 'L') inc = 40;
else if (s[i] == 'X' && s[i + 1] == 'C') inc = 90;
else if (s[i] == 'C' && s[i + 1] == 'D') inc = 400;
else if (s[i] == 'C' && s[i + 1] == 'M') inc = 900;
if (inc > 0) {
total += inc;
i++;
continue;
}
}
if (s[i] == 'I') total += 1;
else if (s[i] == 'V') total += 5;
else if (s[i] == 'X') total += 10;
else if (s[i] == 'L') total += 50;
else if (s[i] == 'C') total += 100;
else if (s[i] == 'D') total += 500;
else if (s[i] == 'M') total += 1000;
}
return total;
}
};