My 7ms solution in java


  • 0
    A

    The solution is solved in 1 pass through the string.
    Runtime should be O(n)
    Memory usage is constant
    Let me know what you think!

    public int romanToInt(String s) {
            String roman = "IVXLCDM";
            int[] num = {1,5,10,50,100,500,1000};
            int prevIdx = roman.indexOf(s.charAt(0));
            int result = num[prevIdx];
            for (int i = 1; i < s.length(); i++) {
                int curIdx = roman.indexOf(s.charAt(i));
                if (prevIdx < curIdx) {
                    result += (num[curIdx] - 2*num[prevIdx]);
                } else {
                    result += num[curIdx];
                }
                prevIdx = curIdx;
            }
            return result;
        }
    

  • 0
    T

    thanks for your solution.
    I think from tail to head is more simple

    public class Solution {
        static String roman = "IVXLCDM";
        static int[] num = {1,5,10,50,100,500,1000};
        public int romanToInt(String s) {
            int result = 0;
            int preIndex = -1;
            for (int i = s.length() - 1; i >= 0; --i) {
                int curIndex = roman.indexOf(s.charAt(i));
                if (preIndex > curIndex) {
                    result -= num[curIndex];
                } else {
                    result += num[curIndex];
                }
                preIndex = curIndex;
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.