13. Roman to Integer

Đề bài

Chữ số La Mã được biểu diễn bằng 7 ký hiệu:

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

Ví dụ:

• 2 viết là II.
• 12 viết là XII (X + II).
• 27 viết là XXVII (XX + V + II).

Thông thường, chữ số La Mã được viết từ trái qua phải theo thứ tự giảm dần. Tuy nhiên có các trường hợp đặc biệt dùng quy tắc “trừ”:

• IV = 4 (5 - 1), IX = 9 (10 - 1)
• XL = 40 (50 - 10), XC = 90 (100 - 10)
• CD = 400 (500 - 100), CM = 900 (1000 - 100)

Cho một chuỗi s là chữ số La Mã, hãy chuyển nó sang số nguyên. Dữ liệu vào đảm bảo nằm trong 1..3999.

Ví dụ 1:

Input: "III"
Output: 3

Ví dụ 2:

Input: "IV"
Output: 4

Ví dụ 3:

Input: "IX"
Output: 9

Ví dụ 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.

Ví dụ 5:

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

Ràng buộc:

• 1 <= s.length <= 15
• s chỉ gồm các ký tự: I, V, X, L, C, D, M
• Kết quả nằm trong 1..3999

Tóm tắt đề

Chuyển chuỗi chữ số La Mã s sang số nguyên theo bảng giá trị và quy tắc cộng/trừ:

• Nếu một ký hiệu có giá trị nhỏ hơn ký hiệu đứng sau nó (ví dụ I trước V) thì sẽ được hiểu là trừ.
• Ngược lại thì cộng.

Ý tưởng

Một cách gọn (đúng như code bên dưới):

• Duyệt từ phải sang trái.
• Lưu biến lastint là giá trị của ký hiệu trước đó (bên phải).
• Với mỗi ký hiệu hiện tại có giá trị num:
  • Nếu num < lastint thì total -= num (trường hợp cần trừ).
  • Ngược lại total += num.
• Cập nhật lastint = num.

Code

package leetcode

var roman = map[string]int{
	"I": 1,
	"V": 5,
	"X": 10,
	"L": 50,
	"C": 100,
	"D": 500,
	"M": 1000,
}

func romanToInt(s string) int {
	if s == "" {
		return 0
	}
	num, lastint, total := 0, 0, 0
	for i := 0; i < len(s); i++ {
		char := s[len(s)-(i+1) : len(s)-i]
		num = roman[char]
		if num < lastint {
			total = total - num
		} else {
			total = total + num
		}
		lastint = num
	}
	return total
}

---