Roman to Integer

Array, Iterative Approach

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9.

• X can be placed before L (50) and C (100) to make 40 and 90.

• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = "III"
Output: 3
Explanation: III = 3.

Example 2:

Input: s = "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 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].

Solutions

The problem is to convert a Roman numeral to an integer. The solution involves a process of iterating over the Roman numeral from left to right. For each character, it adds its corresponding integer value to the result. If a character represents a value that is less than the next character’s value, it subtracts this value instead of adding it. The final result is the integer representation of the original Roman numeral.

Approach - Brute Force Technique

Checks each character in the string one by one.

Steps

1. Dictionary Initialization: A dictionary romanLatters is initialized with Roman numerals as keys and their corresponding integer values as values.

2. Input Validation: The IsValidInput function checks if the input string s is within the valid length (1 to 15 characters) and if all characters in s are valid Roman numerals. If the input string is invalid, the function returns false, and the RomanToInt function will return zero.

3. Roman Numeral Conversion: The RomanToInt function converts the input Roman numeral to an integer. It initializes an integer output to store the result and a variable pre to keep track of the value of the previous Roman numeral.

4. Iteration Over String: The function iterates over each character in the input string s. For each character, it gets the corresponding integer value current from the romanLatters dictionary.

5. Addition and Subtraction: If pre is zero or pre is greater than or equal to current, the function adds current to output. Otherwise, it subtracts pre from output and adds current - pre to output.

6. Update Previous Value: After processing each character, the function updates pre to current.

7. Completion: The function continues this process until all characters in the string have been processed. At this point, output is the integer equivalent of the input Roman numeral.

8. Return Result: Finally, the function returns the integer output.

public class Solution {
    
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
         int output=0;
        if(IsValidInput(s)){
             
           
            int pre=0;
            foreach(char ch in s.ToArray()){
                
                int current=romanLatters[ch];
                if(pre==0 || pre>=current){
                   output+=current;
                }
                else {
                    output = output - pre;
                    output = output + (current-pre);
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the max length of string is 15 characters.

Space Complexity: The space complexity is O(1). The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables output and pre also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.

Approach - Iterative Technique

The solution involves a process of iterating over the Roman numeral from left to right. For each character, it checks if it represents a value that is less than the next character’s value. If it is, it subtracts this value from the result. Otherwise, it adds this value to the result. The final result is the integer representation of the original Roman numeral.

Steps

1. Dictionary Initialization: A dictionary romanLatters is initialized with Roman numerals as keys and their corresponding integer values as values.

2. Input Validation: The IsValidInput function checks if the input string s is within the valid length (1 to 15 characters) and if all characters in s are valid Roman numerals. If the input string is invalid, the function returns false, and the RomanToInt function will return zero.

3. Roman Numeral Conversion: The RomanToInt function converts the input Roman numeral to an integer. It initializes an integer output to store the result.

4. Iteration Over String: The function iterates over each character in the input string s using a for loop. For each character, it gets the corresponding integer value current from the romanLatters dictionary.

5. Addition and Subtraction: Inside the for loop, it checks if the current character’s value is less than the next character’s value. If it is, it subtracts current from output. Otherwise, it adds current to output.

6. Completion: The function continues this process until all characters in the string have been processed. At this point, output is the integer equivalent of the input Roman numeral.

7. Return Result: Finally, the function returns the integer output.

public class Solution {
    public Dictionary<char,int> romanLatters=new Dictionary<char,int>()
    {
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000}
    };
    public int RomanToInt(string s) {
        
        int output=0;
        if(IsValidInput(s)){
             
            int pre=0;
            for(int i=0; i<s.Length; i++){
                
                int current=romanLatters[s[i]];
                if(i+1<s.Length && current<romanLatters[s[i+1]]){
                   output-=current;
                }
                else {
                    output+=current;
                }
                 pre=current;
            }
        }
        return output;
    }
    
    private bool IsValidInput(string input){
        
        return 1<=input.Length && input.Length<=15 &&IsValidRomanInput(input);
    }
    
    private bool IsValidRomanInput(string input){
        
        foreach(char item in input.ToArray()){
             
            if(!romanLatters.ContainsKey(item)){
                return false;
            }
        }
        return true;
    }
}

Complexity

• Time Complexity: O(1)

• Auxiliary Space: O(1)

Time Complexity: The time complexity is O(1). This is because the max length of string is 15 characters.

Space Complexity: The space complexity is O(1). The space used by the program does not grow with the size of the input string. The dictionary of Roman numerals uses a constant amount of space, and the integer variables output and pre also use a constant amount of space.

Please note that this analysis assumes that dictionary lookups can be done in constant time.