Leetcode: 13. Roman to Integer
Converting Roman Numerals to Integer in C++
Today, we are going to discuss a simple but useful C++ class named Solution, which can convert a Roman numeral into an integer.
Class Declaration
class Solution {
public:
unordered_map<char, int> values;
Solution();
int romanToInt(string s);
};
Constructor Implementation
In the constructor, we initialize the map with Roman numerals and their corresponding integer values.
Solution::Solution() {
values = {
{'M', 1000},
{'D', 500},
{'C', 100},
{'L', 50},
{'X', 10},
{'V', 5},
{'I', 1}
};
}
Function Implementation
The function romanToInt converts a Roman numeral string into an integer.
int Solution::romanToInt(string s) {
char lastSymbol = s[s.size() - 1];
int lastValue = values[lastSymbol];
int total = lastValue;
for (int i = s.size() - 2; i >= 0; --i)
{
char currentSymbol = s[i];
int currentValue = values[currentSymbol];
if (currentValue < lastValue)
{
total -= currentValue;
}
else
{
total += currentValue;
}
lastValue = currentValue;
}
return total;
}
Time Complexity Analysis
The time complexity of the romanToInt function is O(n), where n is the length of the input string. This is because we iterate over the string once. Accessing the map value takes constant time, so the overall time complexity remains linear.
Example
Here is how you would use this class:
int main() {
Solution solution;
string roman = "MCMXCIV";
int integer = solution.romanToInt(roman);
cout << "The integer value of " << roman << " is " << integer << endl;
return 0;
}
This would output: "The integer value of MCMXCIV is 1994"
Time and Space Complexity Analysis
The time complexity of the romanToInt function is O(1). As there is a finite set of Roman numerals, the maximum possible number is 3999, which in Roman numerals is MMMCMXCIX. As such, the time complexity is O(1).
If Roman numerals had an arbitrary number of symbols, then the time complexity would be proportional to the length of the input, i.e. O(n). This assumes that looking up the value of each symbol is O(1).
The space complexity is also O(1). Because only a constant number of single-value variables are used, the space complexity is O(1).
Comments
Post a Comment