I figure out a straight look-up table solution... No more thinking on meaningless "effecient decoding" of roman numbers... Since lookup table is generate beforehand the actual running time is O(1).

```
def gen(a,b,c):
return ["", a, a+a, a+a+a, a+b, b, b+a, b+a+a, b+a+a+a, a+c]
m = [gen("I","V","X"),gen("X","L","C"), gen("C","D","M"), gen("M","","")]
r_total_m = dict()
for i in range(4):
for j in range(10):
for k in range(10):
for l in range(10):
r_total_m[m[3][i]+m[2][j]+m[1][k]+m[0][l]]=i*1000+j*100+k*10+l
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
return r_total_m[s]
```