7ms solution in Java. easy to understand


  • 57
    Y
     public int romanToInt(String s) {
        int nums[]=new int[s.length()];
        for(int i=0;i<s.length();i++){
            switch (s.charAt(i)){
                case 'M':
                    nums[i]=1000;
                    break;
                case 'D':
                    nums[i]=500;
                    break;
                case 'C':
                    nums[i]=100;
                    break;
                case 'L':
                    nums[i]=50;
                    break;
                case 'X' :
                    nums[i]=10;
                    break;
                case 'V':
                    nums[i]=5;
                    break;
                case 'I':
                    nums[i]=1;
                    break;
            }
        }
        int sum=0;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]<nums[i+1])
                sum-=nums[i];
            else
                sum+=nums[i];
        }
        return sum+nums[nums.length-1];
    }

  • 0
    H

    great solution


  • 0
    A

    excellent solution! thanks


  • 3
    P

    @yangneu2015 Time limit exceeds for the case "MMMDLXXXVI"


  • 0
    Q

    @yangneu2015 同学,确定是7ms跑出来的代码???我看了一下记录,Java里面最快也用了80ms。。你是不是在本机上测试用了7ms,或者还是啥情况?因为我之前提交的一版本和你的代码很相似,逻辑基本一致不过我用的是Map,没有使用数组,但是显示Time Limit Exceed。


  • 0
    N

    Excellent! Much better than mine.


  • 0
    H

    Hi :D
    My solution to the problem was the exact same logic but using a hash map to store the letter-value pair, instead of using an array. In fact, my solution only goes through the string once and calculates the sum as it goes through but this solution goes through the same length twice (one for reading string, and one more to go through array) My solution was like 109ms i think.
    Could anyone explain why mine is much slower?


  • 1
    A

    I have no idea how that code had runtime 7ms. When I copy paste it I received 83ms :D 70ms I can believe in :)


  • 0

    @amdomanska Likely more test cases have been added in the meantime, or something else in the system has changed.

    Here's another one from around the same time which was also said to have taken 7 ms:
    https://discuss.leetcode.com/topic/27024/java-solution-clean-and-simple-7-ms


  • 0
    A

    @ManuelP Maybe that is true. 7ms looks VERY fast.


  • 0
    N

    Actually, you do not have to run two loops, which could save you a little more time.


  • 0

    share my one-pass solution

    //Ⅰ(1)、Ⅴ(5)、Ⅹ(10)、Ⅼ(50)、Ⅽ(100)、Ⅾ(500)and Ⅿ(1000)
    class Solution {
        public int romanToInt(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }
    
            Map<Character, Integer> map = new HashMap<>();
            map.put('M', 1000);
            map.put('D', 500);
            map.put('C', 100);
            map.put('L', 50);
            map.put('X', 10);
            map.put('V', 5);
            map.put('I', 1);
    
            int sum = 0;
            int prev = map.get(s.charAt(0));
            int next = 0;
    
            for (int i = 1; i < s.length(); i++) {
                next = map.get(s.charAt(i));
    
                if (prev < next) {
                    sum -= prev;
                } else {
                    sum += prev;
                }
    
                //udpare prev because it is like sliding window
                prev = next;
            }
    
            sum += prev;//corner case when only one digit, we need to let sum = prev, so we add prev, not next
            return sum;
        }
    }
    

  • 0
    Q

    I'm 81 years old and I began learning programming last year. This solution is clear enough for me to understand. Thank you OP!


  • 0
    C

    that is so great and easy to understand


  • 0
    S

    @yangneu2015 : Simple and great!


Log in to reply
 

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