Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
Summary: When meeting C/X/I, remembers to search forward to check if there is a bigger number at the front.
1 int romanToInt(string s) { 2 if(s.size() == 0) 3 return 0; 4 5 int num = 0; 6 int m_idx = -1; 7 int d_idx = -1; 8 for(int i = 0; i < s.size(); i ++) { 9 if(s[i] == 'C') { 10 m_idx = s.find_first_of('M', i + 1); 11 d_idx = s.find_first_of('D', i + 1); 12 if(m_idx > i && m_idx < s.size()){ 13 num += 1000 - (m_idx - i)*100; 14 i = m_idx; 15 }else if(d_idx > i && d_idx < s.size()){ 16 num += 500 - (d_idx - i)*100; 17 i = d_idx; 18 }else { 19 num += 100; 20 } 21 }else if( s[i] == 'M'){ 22 num += 1000; 23 }else if(s[i] == 'D') { 24 num += 500; 25 }else if(s[i] == 'L') { 26 num += 50; 27 }else if(s[i] == 'X') { 28 m_idx = s.find_first_of('C', i + 1); 29 d_idx = s.find_first_of('L', i + 1); 30 if(m_idx > i && m_idx < s.size()){ 31 num += 100 - (m_idx - i)*10; 32 i = m_idx; 33 }else if(d_idx > i && d_idx < s.size()){ 34 num += 50 - (d_idx - i)*10; 35 i = d_idx; 36 }else { 37 num += 10; 38 } 39 }else if(s[i] == 'V'){ 40 num += 5; 41 }else if(s[i] == 'I') { 42 m_idx = s.find_first_of('X', i + 1); 43 d_idx = s.find_first_of('V', i + 1); 44 if(m_idx > i && m_idx < s.size()){ 45 num += 10 - (m_idx - i); 46 i = m_idx; 47 }else if(d_idx > i && d_idx < s.size()){ 48 num += 5 - (d_idx - i); 49 i = d_idx; 50 }else { 51 num += 1; 52 } 53 } 54 } 55 return num; 56 }