Roman to Integer

Intuition

Basically, it's all about combination of characters, like this...for example...

cpp

int romanToInt(string s) {
    int sum = 0;
    char prev = ' ';
    for(int i = s.length()-1; i >= 0; i--){
        char ch = s[i];
        if(ch == 'I' && (prev == 'V' || prev == 'X'))
        sum -= 1;
        else if( ch == 'I')
        sum += 1;
        else if(ch == 'V')
        sum += 5;
        else if(ch == 'X' && (prev == 'L' || prev == 'C'))
        sum -= 10;
        else if(ch == 'X')
        sum += 10;
        else if(ch == 'L')
        sum += 50;
        else if(ch == 'C' && (prev == 'D' || prev == 'M'))
        sum -= 100;
        else if(ch == 'C')
        sum += 100;
        else if(ch == 'D')
        sum += 500;
        else if(ch == 'M')
        sum += 1000;
        prev = s[i];
    }
    return sum;
}

Problem can be simpler if we use map, in this case, we have limited keys, so we are using array, to solve this problem. RunTime: 7ms

Code

cpp

int romanToInt(string s) {
	int res = 0, v[200];
	v['I'] = 1, v['V'] = 5, v['X'] = 10, v['L'] = 50, v['C'] = 100, v['D'] = 500, v['M'] = 1000;
	for(int i = 0; i < s.size(); i++) {
		if(i+1 < s.size() && v[s[i]] < v[s[i+1]])
			res += v[s[i+1]] - v[s[i]], i++;
		else
			res += v[s[i]];
	}
	return res;
}

Complexity Analysis

Time: O(n)Space: O(1)

Roman to Integer ​

Intuition ​

Code ​

Complexity Analysis ​

Roman to Integer

Intuition

Code

Complexity Analysis