JAVA solution, not very fast, but most easily to understand.


  • 0
    V
    public class Solution {
        private String helper(int num){
            if(num >= 1000)
                return "M" + helper(num - 1000);
            if(num >= 500)
                return "D" + helper(num - 500);
            if(num >= 100)
                return "C" + helper(num - 100);
            if(num >= 50)
                return "L" + helper(num - 50);
            if(num >= 10)
                return "X" + helper(num - 10);
            if(num >= 5)
                return "V" + helper(num - 5);
            if(num >= 1)
                return "I" + helper(num - 1);
            return "";
        }
        public String intToRoman(int num) {
            String res = helper(num);
            res = res.replace("DCCCC", "CM");
            res = res.replace("CCCC", "CD");
            res = res.replace("LXXXX", "XC");
            res = res.replace("XXXX", "XL");
            res = res.replace("VIIII", "IX");
            res = res.replace("IIII", "IV");
            return res;
            
        }
    }

  • 0
    F

    Do you why it is not a fast solution? If you don't know, I can give you an easy explanation :

    It's because you use a "non tail recursion". A non tail recursion is simply a recursive function which is OBLIGED to store a temporary result while it computes (while it "recurse").

    In your example : when you write this : " return "I" + helper(num - 1); ", your function had to do two main operations : call your helper function in num - 1 AND store "I" as a result. In practice, it's a very bad practice and very consuming!

    You should always avoid non tail recursion as most as possible by writting in your return statement ONLY the name of the recursive function without any other additionnal number. If you want to learn how you can transform a non tail recursion function to a tail recursion, you can see the example in that link of a simple function which calculates the sum of a sequence of numbers : http://stackoverflow.com/questions/33923/what-is-tail-recursion

    That's for my first remark, Second, you can easily replace your many if conditions by a simple switch which is definitely faster and optimal.

    Last remark (as you probably already know) the recursion is not necessary here. Just keep in mind that recursion is a very powerful tool, you should keep it only for complex cases when you can't write an iterative function.

    Hope this could help you a little !


Log in to reply
 

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