1
\$\begingroup\$

I tried to solve the question at https://leetcode.com/problems/roman-to-integer/ i.e Converting an Roman Digit to a Integer using C#. It passes all the test cases but any suggestions to reduce run time and memory usage would be appreciated.

    public static int RomanToInt(string s)
    {
        if (s.Length>=2)
        {
            int currentIndex = s.Length - 1,HighestValue=CharacterValue(s[currentIndex]),number=HighestValue;
            currentIndex--;
            while (currentIndex>=0)
            {
                int currentValue = CharacterValue(s[currentIndex]);
                if(currentValue >= HighestValue)
                {
                    number = number + currentValue;
                    HighestValue = currentValue;
                }

                else
                {
                    number = number - currentValue;
                }

                currentIndex--;
            }

            return number;

        }
        else
        {
            return CharacterValue(s[0]);
        }
    }

    public static int CharacterValue(char c)
    {
        switch (c)
        {
            case 'I': return 1;
            break;
            case 'V':
                return 5;
                break;
            case 'X':
                return 10;
                break;
            case 'L':
                return 50;
                break;
            case 'C':
                return 100;
                break;
            case 'D':
                return 500;
                break;
            case 'M':
                return 1000;
                break;
             default:
                 return 0;
             break;
        }

    }


}
\$\endgroup\$
  • \$\begingroup\$ You want to reduce the runtime but you are not telling us what your current measurements are. Why do you care about it? Do you experience any problems with it? Please also include some example(s) how thi method is supposed to be used. \$\endgroup\$ – t3chb0t Apr 12 at 7:37
  • \$\begingroup\$ Question has been edited \$\endgroup\$ – MANOJ VARMA Apr 12 at 14:36
3
\$\begingroup\$

Run time is linear, and memory usage is constant (and small), so I don't think you're going to see much improvement in either.

You might be able to make some slight improvements by using pointers in unsafe mode (see https://stackoverflow.com/questions/13179554/is-it-faster-to-access-char-in-string-via-operator-or-faster-to-access-char-i), but unless you're processing a very large number of strings this is probably not necessary. As always, profile before and after making any optimizations!

Stylistically, there are a few improvements that could be made:

  • Declare your variables in separate statements.
  • HighestValue should be highestValue.
  • In CharacterValue, you don't need to break when you're returning anyway.
  • It would be clearer to remove the blank line between the inner if and else.
  • You don't need the outer if/else for the length of the string; the code inside the main case would handle a length-1 string fine.
  • The way the logic works, the first item doesn't have to be handled as a special case, so this could be rewritten as a for loop, which would make it (for many people) easier to read.

And one functional one - your code doesn't currently handle the string being null or empty; it should either return 0 or throw an appropriate exception in that case, depending on whether you consider that to be valid input.

So for example:

    public static int RomanToInt(string s)
    {
        if (string.IsNullOrEmpty(s))
        {
            return 0;
        }

        int highestValue = 0;
        int number = 0;

        for(int currentIndex = s.Length - 1; currentIndex >= 0; currentIndex--)
        {
            int currentValue = CharacterValue(s[currentIndex]);

            if (currentValue >= highestValue)
            {
                number += currentValue;
                highestValue = currentValue;
            }
            else
            {
                number -= currentValue;
            }
        }

        return number;
    }

    private static int CharacterValue(char c)
    {
        switch (c)
        {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default:  return 0;
        }
    }
\$\endgroup\$
  • \$\begingroup\$ Thanks for the input.I am curious ,should we declare variables in separate statements in general \$\endgroup\$ – MANOJ VARMA Apr 12 at 10:27
2
\$\begingroup\$

Although your algorithm seems to handle the conversion of the expected chars to numbers and the subtraction and addition rules, it doesn't take care of invalid characters like 'K' or 'b' or any other char. It's not enough to validate against null or empty strings. CharacterValue(char c) defaults to 0 for invalid chars. It would be more appropriate to throw an ArgumentOutOfRangeException with a description of the invalid char.

Besides that, there are a couple of other rules for roman numbers, that you could try to handle. Project Euler has an excellent description of the few rules here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.