Leetcode 13: Roman to Integer
Solution to LeetCode 13: Roman to Integer Problem
Convert a given valid Roman numeral string into its integer equivalent by following the Roman numeral system.
Problem
Approach
Steps
Complexity
Input: The input consists of a string 's', representing a valid Roman numeral.
Example: 'VII'
Constraints:
• 1 <= s.length <= 15
• The string s contains only the characters: 'I', 'V', 'X', 'L', 'C', 'D', 'M'.
• The string s represents a valid Roman numeral in the range [1, 3999].
Output: The output should be the integer equivalent of the Roman numeral string.
Example: 7
Constraints:
• The output will be an integer in the range [1, 3999].
Goal: Convert the Roman numeral string into an integer by processing each character and applying the rules of Roman numerals.
Steps:
• 1. Start with the last character and initialize the result to its corresponding value.
• 2. Iterate through the string from the second-to-last character to the first character.
• 3. If the current character is smaller than the next character (to the right), subtract its value from the result.
• 4. Otherwise, add its value to the result.
• 5. Return the final result.
Goal: The constraints ensure that the input is always a valid Roman numeral within the range [1, 3999].
Steps:
• 1 <= s.length <= 15
• s contains only valid Roman numeral characters ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• The numeral string corresponds to a valid number within the range of 1 to 3999.
Assumptions:
• The input Roman numeral is always valid and within the specified range.
• No additional validation of input is needed.
• Input: 'VII'
• Explanation: 'VII' is interpreted as 5 + 1 + 1 = 7.
• Input: 'IX'
• Explanation: 'IX' is interpreted as 10 - 1 = 9.
Approach: The Roman numeral to integer conversion involves iterating through the string and using the subtraction rule when necessary.
Observations:
• Roman numerals have specific rules for subtraction, such as 'IV' for 4 and 'IX' for 9.
• By iterating over the string from right to left, we can easily handle the subtraction rule.
• We need to keep track of the current character and compare it with the next one to determine whether to add or subtract its value.
Steps:
• 1. Define a helper function that returns the integer value for each Roman numeral character.
• 2. Start from the last character of the string and initialize the result with its value.
• 3. Iterate through the string, from right to left, adjusting the result based on the subtraction rule.
• 4. Return the final computed result after processing all characters.
Empty Inputs:
• The input is guaranteed to be valid and non-empty.
Large Inputs:
• Ensure that the solution works within the constraint of 15 characters.
Special Values:
• The smallest valid Roman numeral is 'I' (1), and the largest is 'MMMCMXCIX' (3999).
Constraints:
• The input is always a valid Roman numeral within the range [1, 3999].
int romanToInt(string s)
{
int ln = s.length();
int res= RomToNum(s[ln-1]);
int prv= res, curr = 0;
for (int i = ln -2; i >=0; i--)
{
curr = RomToNum(s[i]);
(curr < prv)? (res -= curr): (res += curr);
prv = curr;
}
return res;
}
int RomToNum(char s)
{
switch (s)
{
case 'I' : return 1 ;
case 'V' : return 5 ;
case 'X' : return 10 ;
case 'L' : return 50 ;
case 'C' : return 100 ;
case 'D' : return 500 ;
case 'M' : return 1000 ;
}
return 0;
}
1 : Function Declaration
int romanToInt(string s)
Declare the `romanToInt` function, which takes a Roman numeral string `s` as input and returns its integer value.
2 : Variable Initialization
int ln = s.length();
Initialize `ln` to store the length of the input Roman numeral string.
3 : Variable Initialization
int res= RomToNum(s[ln-1]);
Initialize `res` with the integer value of the last Roman numeral character.
4 : Variable Initialization
int prv= res, curr = 0;
Initialize `prv` (previous) to the value of the last character and `curr` (current) to 0.
5 : Loop Iteration
for (int i = ln -2; i >=0; i--)
Start a loop to iterate through the Roman numeral string from the second-to-last character to the first.
6 : Variable Assignment
curr = RomToNum(s[i]);
Assign the integer value of the current character to `curr`.
7 : Conditional Update
(curr < prv)? (res -= curr): (res += curr);
Check if the current value is less than the previous value. If so, subtract it from `res`; otherwise, add it.
8 : Variable Assignment
prv = curr;
Update `prv` to the current value for the next iteration.
9 : Return Value
return res;
Return the final integer value `res`.
10 : Function Declaration
No explicit declaration here, as `RomToNum` is a helper function defined within the same code block.
11 : Function Body
int RomToNum(char s)
Declare the `RomToNum` helper function, which takes a Roman numeral character `s` and returns its integer value.
12 : Conditional Check
switch (s)
Use a `switch` statement to check the value of the character `s`.
13 : Case 1
case 'I' : return 1 ;
If `s` is 'I', return 1.
14 : Case 2
case 'V' : return 5 ;
If `s` is 'V', return 5.
15 : Case 3
case 'X' : return 10 ;
If `s` is 'X', return 10.
16 : Case 4
case 'L' : return 50 ;
If `s` is 'L', return 50.
17 : Case 5
case 'C' : return 100 ;
If `s` is 'C', return 100.
18 : Case 6
case 'D' : return 500 ;
If `s` is 'D', return 500.
19 : Case 7
case 'M' : return 1000 ;
If `s` is 'M', return 1000.
20 : Default Case
}
End of the `switch` statement.
21 : Return Value
return 0;
If the character is not a valid Roman numeral, return 0.
Best Case: O(n), where n is the length of the string s.
Average Case: O(n), since the iteration over the string is always linear.
Worst Case: O(n), since we process each character once.
Description: The time complexity is linear because we iterate over the Roman numeral string once.
Best Case: O(1), as the space usage does not depend on the input size.
Worst Case: O(1), since only a few variables are used to store the result.
Description: The space complexity is constant, as we only use a few variables to compute the result.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus