06. Roman Number to Integer
✅ GFG solution to Roman Number to Integer problem: convert Roman numerals to decimal using greedy pattern matching technique for optimal performance. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given a string s in Roman number format, your task is to convert it to an integer. Various symbols and their values are given below:
Roman Numeral Values:
I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000
Special Cases (Subtraction Rules):
IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900
The goal is to parse the Roman numeral string and return its equivalent decimal integer value.
📘 Examples
Example 1
Input: s = "IX"
Output: 9
Explanation: IX is a Roman symbol which represents 10 – 1 = 9.Example 2
Input: s = "XL"
Output: 40
Explanation: XL is a Roman symbol which represents 50 – 10 = 40.Example 3
Input: s = "MCMIV"
Output: 1904
Explanation: M is 1000, CM is 1000 – 100 = 900, and IV is 4.
So we have total as 1000 + 900 + 4 = 1904.🔒 Constraints
$1 \le \text{roman number} \le 3999$
$s[i] \in [I, V, X, L, C, D, M]$
✅ My Approach
The optimal approach uses a Greedy Pattern Matching technique that processes Roman numerals from largest to smallest values:
Greedy Pattern Matching Algorithm
Initialize Data Structures:
Create parallel arrays:
vals[]for decimal values andsyms[]for corresponding Roman patterns.Order them from largest to smallest value (M=1000 down to I=1).
Include subtraction cases (CM=900, CD=400, XC=90, XL=40, IX=9, IV=4).
Greedy Matching:
For each Roman pattern in descending order of value:
Check if current position in string matches the pattern.
If match found, add its value to result and advance position by pattern length.
Repeat until no more matches for current pattern.
Process All Patterns:
Continue with next smaller pattern until all 13 patterns are processed.
This ensures larger values are consumed first (greedy approach).
Return Result:
The accumulated sum represents the decimal equivalent.
Key Insight: By processing patterns in descending order, we naturally handle subtraction cases (like CM, CD) before their individual components, ensuring correct interpretation.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the length of the Roman numeral string. Each character is processed at most once as we advance through the string systematically.
Expected Auxiliary Space Complexity: O(1), as we use fixed-size arrays for storing the 13 Roman patterns and their values, requiring constant extra space regardless of input size.
🧑💻 Code (C++)
class Solution {
public:
int romanToDecimal(string s) {
int vals[] = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
string syms[] = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int res = 0, i = 0;
for (int j = 0; j < 13; j++) {
while (i + syms[j].length() <= s.length() && s.substr(i, syms[j].length()) == syms[j]) {
res += vals[j];
i += syms[j].length();
}
}
return res;
}
};☕ Code (Java)
class Solution {
public int romanToDecimal(String s) {
int[] vals = {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String[] syms = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
int res = 0, i = 0;
for (int j = 0; j < 13; j++) {
while (i + syms[j].length() <= s.length() && s.substring(i, i + syms[j].length()).equals(syms[j])) {
res += vals[j];
i += syms[j].length();
}
}
return res;
}
}🐍 Code (Python)
class Solution:
def romanToDecimal(self, s):
vals = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
syms = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
res = i = 0
for j in range(13):
while i + len(syms[j]) <= len(s) and s[i:i+len(syms[j])] == syms[j]:
res += vals[j]
i += len(syms[j])
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated