13. Roman to Integer

# Easy

Two pointers problem. One is current, the other one is next. Only two situations:

1. roman{cur} < roman{next}, such as 90 = 100 - 10, num{90} = 'XC'

2. roman{cur} >= roman{next}, eg1, 110 = 100 + 10, num{110} = 'CX', eg2, num{80} = 'LXXX'

其实不容易想到。

Solution:

1. if roman{cur} < roman{next}, two letters must be computed together, cur and next pointers are moved 2 steps.

2. if roman{cur} >= roman{next}, then only collect roman{cur}, cur and next pointers are moved 1 step.

3. Don't forget to consider one last edge situation, if cur points to last element, add it to num directly, if cur points out of range, ignore it.

Python

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        roman = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C':100, 'D': 500, 'M': 1000}
        # edge case
        if len(s) == 1:
            return roman[s[0]]
        
        # regular case
        cur = 0
        nex = 1
        num = 0
        while nex < len(s):
            if roman[s[cur]] < roman[s[nex]]:   # bind two letters (such as 90, 'XC')
                num += roman[s[nex]] - roman[s[cur]]
                cur += 2
                nex += 2
            else:   # only one single letter (such as 100~'C', 80~'LXXX')
                num += roman[s[cur]]
                cur += 1
                nex += 1
        
        if cur == len(s) - 1:
            num += roman[s[cur]]
            
        return num