13.roman-to-integer.md

問題

https://leetcode.com/problems/roman-to-integer

回答

初回の回答: HashMap と peekable()を使い左から順にパースしていく方針。

最初問題を読んだとき、コンパイラのパースと似ているなと思った。なので、過去に実装した ueyama rui さんの C コンパイラのリポジトリを見に行き、トークン化する部分のコードを参考にした。 peekable()という iterator の要素を一つ先読みできるメソッドを見つけたのでそれを使って、1 文字~2 文字の組み合わせをパースしていこうと思った。結果として、結構な if 分岐ができてしまってもう少し単純化できそうなコードになってしまった。

use std::collections::HashMap;
impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let mut chars = s.trim().chars().peekable();
        let singles = HashMap::from([
            ('I', 1),
            ('V', 5),
            ('X', 10),
            ('L', 50),
            ('C', 100),
            ('D', 500),
            ('M', 1000),
        ]);
        let doubles = HashMap::from([
            ("IV".to_string(), 4),
            ("IX".to_string(), 9),
            ("XL".to_string(), 40),
            ("XC".to_string(), 90),
            ("CD".to_string(), 400),
            ("CM".to_string(), 900),
        ]);
        let mut sum = 0;
        while let Some(_) = chars.peek() {
            let s = chars.next().unwrap();
            match chars.peek() {
                Some(t) => {
                    match doubles.get(&format!("{}{}", s, t)) {
                        Some(double) => {
                            sum += double;
                            chars.next();
                        }
                        None => {
                            if let Some(single) = singles.get(&s) {
                                sum += single;
                            }
                        }
                    };
                }
                None => {
                    if let Some(single) = singles.get(&s) {
                        sum += single;
                    }
                }
            }
        }
        sum
    }
}

---

二回目の回答: HashMap と&str を使い左から順にパースしていく方針。

わざわざ peekable()を挟まなくても string slice にして for 文回せば同じようなことはできる。けど、初回回答と同じ実行時間 12ms だった。

use std::collections::HashMap;
impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        let values = HashMap::from([
            ("I", 1),
            ("V", 5),
            ("X", 10),
            ("L", 50),
            ("C", 100),
            ("D", 500),
            ("M", 1000),
            ("IV", 4),
            ("IX", 9),
            ("XL", 40),
            ("XC", 90),
            ("CD", 400),
            ("CM", 900),
        ]);

        let s_str = &s[..];
        let (mut i, mut sum) = (0, 0);
        while i < s_str.len() {
            if i < s_str.len() - 1 {
                if let Some(n) = values.get(&s_str[i..=i + 1]) {
                    sum += n;
                    i += 2;
                    continue;
                }
            }
            if let Some(n) = values.get(&s_str[i..i + 1]) {
                sum += n;
            }
            i += 1;
        }
        sum
    }
}

---

三回目の回答: 右から順にパースして数値が逆転する場合のみ減算していく方針。

これはほぼおまけ。問題を知ってる人があーそれねって感じで思いつくもんだと思う。よく考えたなこれ。

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        s.trim().chars().rev().fold(0, |acc, x| -> i32 {
            acc + match x {
                'I' if acc == 5 || acc == 10 => -1,
                'I' => 1,
                'V' => 5,
                'X' if acc >= 50 => -10,
                'X' => 10,
                'L' => 50,
                'C' if acc >= 500 => -100,
                'C' => 100,
                'D' => 500,
                'M' => 1000,
                _ => panic!(),
            }
        })
    }
}