DEV Community

shine
shine

Posted on

[📝LeetCode #13] Roman to Integer

#leetcode #100daysofcode #hashmap #java

🎀 The Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Given a roman numeral, convert it to an integer.

Example:

Input: s = "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

👩‍💻 My Answer 

class Solution { public int romanToInt(String s) { int sum = 0; int i; for (i = 0; i < s.length() - 1; i++) { char letter = s.charAt(i); if (letter == 'M') sum += 1000; else if (letter == 'D') sum += 500; else if (letter == 'C' && s.charAt(i+1) == 'D') { sum += 400; i++; } else if (letter == 'C' && s.charAt(i+1) == 'M') { sum += 900; i++; } else if (letter == 'C') sum += 100; else if (letter == 'L') sum += 50; else if (letter == 'X' && s.charAt(i+1) == 'C') { sum += 90; i++; } else if (letter == 'X' && s.charAt(i+1) == 'L') { sum += 40; i++; } else if (letter == 'X') sum += 10; else if (letter == 'V') sum += 5; else if (letter == 'I' && s.charAt(i+1) == 'X') { sum += 9; i++; } else if (letter == 'I' && s.charAt(i+1) == 'V') { sum += 4; i++; } else if (letter == 'I') sum += 1; } if (i == s.length() - 1) { char letter = s.charAt(i); if (letter == 'M') sum += 1000; else if (letter == 'D') sum += 500; else if (letter == 'C') sum += 100; else if (letter == 'L') sum += 50; else if (letter == 'X') sum += 10; else if (letter == 'V') sum += 5; else if (letter == 'I') sum += 1; } return sum; } }
Enter fullscreen mode Exit fullscreen mode

Runtime & Memory

Pro & Con

  • ✅ Runtime
  • ✖️ Too long
  • ✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach - "HashMap"

I used the charAt and if statement to go through the array. But, I read the solution on LeetCode and they used the HashMap.

New Code 

class Solution { public int romanToInt(String s) { Map<Character, Integer> map = new HashMap(); map.put('I', 1); map.put('V', 5); map.put('X', 10); map.put('L', 50); map.put('C', 100); map.put('D', 500); map.put('M', 1000); int sum = 0; for (int i = 0; i < s.length(); i++) { if (i == s.length() - 1) { sum += map.get(s.charAt(i)); break; } int current = map.get(s.charAt(i)); int next = map.get(s.charAt(i+1)); if (current >= next) sum += current; else { sum += next - current; i++; } } return sum; } }
Enter fullscreen mode Exit fullscreen mode

New Runtime & Memory

It still beats 55%, not 100%. So, I checked and saw the ideal code on LeetCode. Here is:

class Solution { public int romanToInt(String s) { Map<Character, Integer> m = new HashMap<>(); m.put('I', 1); m.put('V', 5); m.put('X', 10); m.put('L', 50); m.put('C', 100); m.put('D', 500); m.put('M', 1000); int ans = 0; for (int i = 0; i < s.length(); i++) { if (i < s.length() - 1 && m.get(s.charAt(i)) < m.get(s.charAt(i + 1))) { ans -= m.get(s.charAt(i)); } else { ans += m.get(s.charAt(i)); } } return ans; } }
Enter fullscreen mode Exit fullscreen mode

WAITTTT! I ran the "BEST" code, and it still DOES NOT beat 100%. (This was almost the same as my New Code.) So, I searched more and I think using switch condition is the best for Java, and the code below actually beat 100% (I ran!):

class Solution { public int romanToInt(String s) { int answer = 0, number = 0, prev = 0; for (int j = s.length() - 1; j > -1; j--) { number = switch (s.charAt(j)) { case 'M' -> 1000; case 'D' -> 500; case 'C' -> 100; case 'L' -> 50; case 'X' -> 10; case 'V' -> 5; case 'I' -> 1; default -> 0; }; answer += number; if (number < prev) answer -= 2 * number; prev = number; } return answer; } }
Enter fullscreen mode Exit fullscreen mode

💡 What I Learned

  • How to use HashMap 
Map<>() map = new HashMap(); map.put(KEY, VALUE); map.get(KEY);
Enter fullscreen mode Exit fullscreen mode

  • Use '' for char and "" for array

  • There are many FAKE solution posts on LeetCode.

Top comments (0)

Some comments may only be visible to logged-in visitors. Sign in to view all comments.