59. String to Integer (atoi)

読了目安約2分

その他 / LeetCode 8 (Medium) — 文字列を規則に従って 32bit 整数に変換する

この章の目次

問題

LeetCode 8. String to Integer (atoi)（Medium / カテゴリ: その他）

文字列 s を次の規則で整数に変換する問題です。

先頭の空白を読み飛ばす
次の 1 文字が + か - なら符号として読む
続く数字の並びを整数として読み、数字が途切れたら以降は無視する
数字が 1 文字もなければ 0 を返す
結果が 32bit 符号付き整数の範囲を超えるなら 2147483647 (Int32.max) か -2147483648 (Int32.min) に丸める

例: " -042" は -42、"1337c0d3" は 1337、"words and 987" は 0 です。

考え方

ヒント 1

処理は「空白 → 符号 → 数字」の一方通行です。 [Character] にして、添字を進めながら 3 段階を順に処理します。

ヒント 2

数値は result = result * 10 + 桁 で 1 桁ずつ組み立てます。 1 桁足すたびに 32bit の範囲を確認し、超えたらその場で丸めた値を返します。最後にまとめて確認する方式は、数字が何百桁も続く入力で Int すら溢れるので使えません。

Swift 実装のポイント

戻り値の型は Int ですが、値は 32bit の範囲に丸めます。境界は Int(Int32.max) と Int(Int32.min) で Int の値として書けます。
Swift の Int は 64bit なので、1 桁足すごとに範囲を確認していれば途中計算は溢れません。
Character の wholeNumberValue は数字なら値を、それ以外なら nil を返します。while i < chars.count, let d = chars[i].wholeNumberValue の形で「数字が続く間」のループが書けます。

模範解答

Swift
class Solution {
    func myAtoi(_ s: String) -> Int {
        let chars = Array(s)
        var i = 0
        while i < chars.count && chars[i] == " " {
            i += 1
        }
        var sign = 1
        if i < chars.count && (chars[i] == "+" || chars[i] == "-") {
            if chars[i] == "-" { sign = -1 }
            i += 1
        }
        var result = 0
        while i < chars.count, let d = chars[i].wholeNumberValue, (0...9).contains(d) {
            result = result * 10 + d
            if sign == 1 && result > Int(Int32.max) { return Int(Int32.max) }
            if sign == -1 && -result < Int(Int32.min) { return Int(Int32.min) }
            i += 1
        }
        return sign * result
    }
}

計算量: O(n)。