【ITニュース解説】LeetCode 8: String to Integer (atoi) - Medium

LeetCodeの「String to Integer (atoi)」問題は、文字列で表現された数字を実際の整数型に変換するという、システムエンジニアを目指す初心者にとって非常に基礎的かつ重要なプログラミング課題である。一見単純に思えるこの問題だが、実際には多くの考慮すべき点があり、現実世界で文字列を扱う際の複雑さを理解するための良い訓練となる。

この問題の目標は、例えば " -42" や "4193 with words"、"+123" のような文字列を入力として受け取り、それらをそれぞれ -42、4193、123といった整数に正確に変換することだ。しかし、これにはいくつかの厳密なルールがある。

まず、先頭の空白を無視する必要がある。つまり、文字列の冒頭に存在するスペースはすべて読み飛ばし、最初の非空白文字から処理を開始しなければならない。次に、正負の符号を適切に処理することが求められる。数字の前に '+' や '-' があれば、その符号を認識し、結果に反映させる。もし符号がなければ、その数字は正数として扱う。さらに、数字以外の文字が現れたらそこで処理を停止するというルールがある。例えば "4193 with words" の場合、"4193"までは数字として変換するが、' '（スペース）が現れた時点で変換を終了し、" with words" の部分は無視する。

最も重要な制約の一つに、32ビット符号付き整数（int型）の範囲を遵守するというものがある。これは、結果の数値が約 -21億から +21億の範囲に収まっている必要があるという意味だ。もし計算途中でこの範囲を超えそうになったり、実際に超えてしまった場合は、符号に応じて int.MaxValue（最大値）または int.MinValue（最小値）を返さなければならない。最後に、もし文字列が空であるか、または有効な数字が全く含まれていない場合は、デフォルトとして0を返す必要がある。

提示された解決策は、これらの要件を非常に効率的に満たすように設計されている。この方法では、文字列の文字を一つ一つ直接インデックスで操作し、不要な文字列操作（例えば、文字列全体の先頭・末尾の空白を除去する .Trim() のようなメソッド）を避けることで、処理のオーバーヘッドを最小限に抑えている。結果として、0ミリ秒の実行時間（提出された他の解答の100%よりも速い）と、比較的少ないメモリ使用量（50%の提出よりも良い）を達成している。

具体的な解決ステップは次のようになる。

最初に、入力された文字列が null（存在しない）であるか、または空文字列であるかをチェックする。もしそうであれば、ルールに従って0を返す。

次に、文字列の現在の処理位置を示す idx というインデックス変数を用意し、先頭の空白文字をスキップする。whileループを使って、idxが文字列の終端に達しておらず、かつ現在の文字がスペースである限り、idxを一つずつ進めていく。もしこの処理で idx が文字列の終端まで到達してしまった場合、文字列には数字が含まれていなかったため、0を返す。

続いて、数字の符号を決定する。signという変数を1で初期化し、デフォルトで正数として扱う。もし現在の文字が '+' または '-' であれば、signをそれぞれ1または-1に更新し、idxを一つ進めて次の文字に移動する。

いよいよ数字を構築していく。 result という変数を0で初期化し、ここに変換された整数を蓄積する。再度 whileループを使用し、idxが文字列の終端に達しておらず、かつ現在の文字が数字である限り、ループを続ける。 ループの中で、まず現在の文字を実際の数値に変換する。例えば、文字の '5' から文字の '0' を引くと、数値の5が得られる。これを digit とする。 そして、この新しいdigitをresultに加える前に、オーバーフローのチェックを行う。これはこの問題で最も重要な部分だ。次に計算される result * 10 + digit が int.MaxValue（正数の最大値）を超えないかを事前に確認する。具体的なチェックは result > (int.MaxValue - digit) / 10 という式で行われる。 この式は、もしresultが既に(int.MaxValue - digit) / 10よりも大きい値になっていれば、resultを10倍してdigitを加えることで確実にオーバーフローすることを意味する。例えば、int.MaxValueが2147483647として、現在のresultが214748364で、次のdigitが8だった場合を考える。214748364 > (2147483647 - 8) / 10という式は 214748364 > 214748363.9 となり真となる。これは、次のresult * 10 + digitが2147483648となり、int.MaxValueを超えてしまうことを事前に検知しているのだ。もしオーバーフローが検出された場合、signが正なら int.MaxValueを、負なら int.MinValueを即座に返す。 オーバーフローの心配がなければ、resultを10倍し、現在のdigitを加えていく（result = result * 10 + digit;）。これにより、例えば "123" という文字列の場合、最初は 0*10+1=1、次に 1*10+2=12、最後に 12*10+3=123 といった具合に、数字が正しく構築されていく。この後、idxを一つ進めて次の文字へ移動する。

すべての数字の処理が完了したら、最後に result に sign を掛けることで、最終的な正または負の整数値を得る。例えば、resultが123でsignが-1であれば、123 * -1 = -123 となり、正しい結果が返される。

このように、この解決策は文字列の各文字を直接操作し、早期にエラーを検出し、特にオーバーフローのような複雑なケースも効率的かつ堅牢に処理することで、文字列から整数への変換という一見単純な問題を、あらゆるエッジケースに対応できるように解決している。