[LeetCode 13] Roman to Integer

This is the reverse of the previous problem.

Hehe, my first sneaky thought was to use the previous problem’s code to build a lookup table for all numbers up to 3999, but I felt that would be too cheap.

So I decided to solve it properly.

Of course, the previous solution had way too many switch statements and if-else blocks.

So I decided to improve the approach.

Here’s the code – AC on the first try again:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    int num;
    int romanToInt(string s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        num = 0;
        string sub[] = {
            "CM","DCCC","DCC","DC","D","CD","CCC","CC","C",
            "XC","LXXX","LXX","LX","L","XL","XXX","XX","X",
            "IX","VIII","VII","VI","V","IV","III","II","I"
        };
        int q[] = {
            900,800,700,600,500,400,300,200,100,
            90,80,70,60,50,40,30,20,10,
            9,8,7,6,5,4,3,2,1
        };
        int i;
        for(i = 0;i < s.size();i++)
        {
            if(s[i] != 'M')
                break;
            else
                num += 1000;
        }
        s = s.substr(i,s.size());
        for(int i = 0;i < 27;i++)
        {
            s = stringtoint(s,i,sub,q);
        }
        return num;
    }
    string stringtoint(string s,int i,string sub[],int q[])
    {
        if(finds(s,sub[i]))
        {
            num += q[i];
            s = s.substr(sub[i].length(),s.size()-1);
        }
        return s;
    }
    bool finds(string s,string sub)
    {
        if(s.size() < sub.size())
            return false;
        for(int i = 0;i < sub.size();i++)
        {
            if(s[i] != sub[i])
                return false;
        }
        return true;
    }
};