ac solution code


  • 0

    Solution1. time = O(n); space = O(1)

    KEY:

    • Roman digits are based on SUM from end to start, not multiplication!!

    Explanation:

    1. map: [Number: RomanString]. 10 * 4 table to present Roman strings corresponding to 10-digit value
      • 1...9
      • 10...90
      • 100...900
      • 1000...3000
    2. Decial digit: from low to high - divided by 10 each step
    3. Prefix Roman String to prev result
      • Check Roman string in the table corresponding to the remainder
    func intToRoman(_ num: Int) -> String {
                                                                                     // 10 * 4 map: Digit => String
        let map    =   [["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],// 1..9
                        ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],// 10..90
                        ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],// 100..900
                        ["", "M", "MM", "MMM"]]                                      // 1000..3000
        
        var res = ""
        var digit = 0, num = num
        while num > 0 {                         // Start from low to high digit: 1=>1000 (Same as 10-digit decimal system: low->high = right->left)
            let curVal = num % 10
            let curStr = map[digit][curVal]     // Current 10-digit value
            res = curStr + res                  // Prefix Roman string to result
            
            num /= 10                           // Advance to next digit (lefter)
            digit += 1
        }
        return res
    }
    

Log in to reply
 

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