C# solution with explanation, one pass and constant memory


  • 0
    R
    public class Solution {
        public int RomanToInt(string s) {
            if (s == null || s.Length == 0)
                return 0;
            // The conversion table, also could be done with a switch statement
            Dictionary<char, int> digitValues = new Dictionary<char, int>()
            {
                {'I', 1},
                {'V', 5},
                {'X', 10},
                {'L', 50},
                {'C', 100},
                {'D', 500},
                {'M', 1000}
            };
            // The total sum
            int total = 0;
            // The accumulator to hold an intermediate sum
            int acc = 0;
            // The value of a previously seen digit
            // set initially to 1000 (actually, any number >=1000 will do)
            // to avoid firing the second branch of the if further down
            int prevVal = 1000;
            foreach (char c in s)
            {
                // Get the value of the current digit
                int val = digitValues[c];
                if (val < prevVal) // If it's less than the previously digit (for instance XI)
                {
                    // Add the currently accumulated value to the total sum
                    total += acc;
                    // Start building a new value
                    // the current digit hasn't been used in the total sum, so put it in acc
                    acc = val;
                }
                else if (val > prevVal)  // If it's greater than the previous digit (for instance IX)
                {
                    // Subtract the accumulated value from the current value and add the result to the total sum
                    total += (val - acc);
                    // Start building a new value
                    // the current digit is already used in calculation, set acc to zero
                    acc = 0;
                }
                else  // If it's equal to the previous digit (XX)
                {
                    // Simply add it to acc
                    acc += val;
                }
                prevVal = val;  // Update the previous digit value
            }
            // The final addition of acc to the total sum
            total += acc;
    
            return total;
        }
    }
    

    Let's see how it works with the value of 905, which is CMV

    • total = 0, acc = 0, prevVal = 1000
      the character is "C", val = 100: 100 < 1000 => the first branch total += acc; acc = val
    • total = 0, acc = 100, prevVal = 100
      the character is "M", val = 1000, 1000 > 100 => the second branch total += (val - acc); acc = 0
    • total = 900, acc = 0, prevVal = 1000
      the character is "V", val = 5, 5 < 1000 => the first branch total += acc; acc = val
    • After the loop total = 900 and acc = 5, it's added to the total for the final value of 905

    Let's see how it works with 551, which is DLI

    • total = 0, acc = 0, prevVal = 1000
      the character is "D", val = 500: 500 < 1000 => the first branch total += acc; acc = val
    • total = 0, acc = 500, prevVal = 500
      the character is "L", val = 50: 50 < 500 => the first branch total += acc; acc = val
    • total = 500, acc = 50, prevVal = 50
      the character is "I", val = 1, 1 < 50, the first branch total += acc; acc = val
    • After the loop total = 550 and acc = 1, it's added to the total for the final value of 551

    Let's see how it works with 209, which is CCIX

    • total = 0, acc = 0, prevVal = 1000
      the character is "C", val = 100: 100 < 1000 => the first branch total += acc; acc = val
    • total = 0, acc = 100, prevVal = 100
      the character is "C", val = 100: 100 = 100 => the third branch acc += val
    • total = 0, acc = 200, prevVal = 100
      the character is "I", val = 1: 1 < 100, the first branch total += acc; acc = val
    • total = 200, acc = 1, prevVal = 1
      the character is "X", val = 10: 10 > 1 the second branch total += (val - acc); acc = 0
    • After the loop total = 209 and acc = 0, it's added to the total for the final value of 209

Log in to reply
 

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