プロンプトと適用範囲
これはビット操作と文字エンコーディングに関する問題です。入力はバイト配列であり、すでにデコードされた Unicode 文字列ではありません。各スカラーが 1〜4 バイトを使用しているかを判定し、途中で途切れているシーケンスや不正な形式のシーケンスを拒否します。LeetCode 393 でも同じ制約が使用されます。長さは最大 2 * 10^4 で、各整数はその下位 8 ビットを提供します。RFC 3629 では 1〜4 バイトの UTF-8 形式と有効なスカラー値の範囲が定義されています。
面接官が見ているポイント
- 先頭バイトのパターンから後続バイト数を導出できるか。
10xxxxxxの後続プレフィックスを厳格にチェックできるか。- 余分な後続バイト、途切れ、5 バイトの先頭パターンを拒否できるか。
- 時間計算量
O(n)、追加空間計算量O(1)の 1 パス処理を実現できるか。
最初に確認すべき明確化事項
すべての要素が 0..255 の範囲内にあることが保証されているか確認します。保証されていない場合は、まず範囲外の値を拒否します。また、タスクがバイト形状（プレフィックス）のみをチェックするのか、それとも過長エンコーディング（overlong encoding）、サロゲートコードポイント、U+10FFFF を超える値も拒否する必要があるのかを明確にします。LeetCode 版はバイト形状に焦点を当てていますが、本番環境のパーサーではより厳格な RFC 3629 のスカラー値ルールを適用する必要があります。
30秒での回答
現在の文字にまだ必要な後続バイト数を示す remaining を保持します。先頭バイトの場合は、その上位ビットパターンを使用して 0、1、2、または 3 を設定します。後続バイトの場合は、(byte & 0b11000000) === 0b10000000 を要求し、カウンタをデクリメントします。不正な先頭バイト、予期しない後続バイト、または remaining !== 0 の状態での入力終了は拒否します。スキャンで保持するのはこのカウンタのみです。
ステップごとの解説
1. 先頭バイトのパターンを認識する
0xxxxxxx は 1 バイト文字です。110xxxxx、1110xxxx、11110xxx はそれぞれ 1、2、3 個の後続バイトを必要とします。マスクを使用してプレフィックスをテストします。まず 0x80 をチェックし、次に 0xE0、0xF0、最後に 0xF8 をチェックします。0xF8 テストが依然として非ゼロである場合、そのバイトは 5 バイト以上の形式を開始しているため、拒否する必要があります。
2. 後続バイトをオンラインで検証する
remaining > 0 の場合、現在のバイトは 10xxxxxx に一致する必要があります。チェックが成功したらデクリメントします。この状態での ASCII 先頭バイトや別のマルチバイト先頭バイトは直ちに無効となります。バックトラックやスライスは不要で、入力終了時に途切れが検出されます。
3. 参照実装
isValidUtf8(bytes):
remaining = 0
for byte in bytes:
if byte < 0 or byte > 255: return false
if remaining > 0:
if (byte & 0b11000000) != 0b10000000: return false
remaining -= 1
continue
if (byte & 0b10000000) == 0:
remaining = 0
else if (byte & 0b11100000) == 0b11000000:
remaining = 1
else if (byte & 0b11110000) == 0b11100000:
remaining = 2
else if (byte & 0b11111000) == 0b11110000:
remaining = 3
else:
return false
return remaining == 04. 本番レベルの厳格さ
プレフィックスのカウントだけでは、1 バイトで済む値を 3 バイトで表現するような過長エンコーディングの一部を受け入れてしまい、サロゲート値も受け入れてしまう可能性があります。本番環境のパーサーはスカラー値を蓄積し、その長さに対応する最小値、サロゲート範囲、および U+10FFFF の上限をチェックする必要があります。また、BOM が許可されるかどうかを明示的に決定します。ルールを暗黙的に混ぜるのではなく、まず演習の境界を述べてから、この拡張について説明します。
5. テストと計算量
[197,130,1]（true）、[235,140,4]（false）、孤立した後続バイト [128]、途切れたシーケンス [226,130]、5 バイトの先頭バイト [248,128,128,128,128]、および空配列をテスト対象とします。各バイトは 1 回スキャンされます。配列の長さを n とすると、時間計算量は O(n)、追加空間計算量は O(1) です。
模範回答
先頭バイトの認識と後続バイトの検証を分離して処理します。0xxxxxxx、110xxxxx、1110xxxx、または 11110xxx に一致する先頭バイトは、remaining をそれぞれ 0、1、2、または 3 に設定します。後続状態では 10xxxxxx のみを受け入れ、カウンタをデクリメントします。5 バイトの先頭バイト、予期しない後続バイト、範囲外の要素、または不完全な文字のままでの入力終了は false を返します。実装は O(n) 時間、O(1) 空間の 1 パスです。本番環境向けには、スカラー値を蓄積して過長エンコーディング、サロゲート、および U+10FFFF を超える値を拒否します。
よくある間違い
- 各
10プレフィックスをチェックせずに後続バイトをカウントしてしまう。 111110xxを有効な 5 バイト形式として扱ってしまう。- 最後の
remainingチェックを忘れて、途切れたシーケンスを受け入れてしまう。 - ビットレベルの不変条件やエラーインデックスを示さずに、言語組み込みのデコーダに委託してしまう。
- 適用範囲を明示せずに、LeetCode の形状チェックと RFC のスカラー値ルールを混同してしまう。
byteを符号付きとして扱い、ビット操作の前に0..255に正規化しない。
関連する質問
最初のエラーインデックスを返すにはどうすればよいですか？
{valid, errorIndex, reason} を返します。先頭バイト、後続バイト、または入力終了のチェックが失敗したときに、現在のインデックスを記録します。スキャン状態はそのまま保持されるため、呼び出し側は元のバイトを強調表示できます。
チャンク化されたストリーミング入力をサポートするにはどうすればよいですか？
チャンク間で remaining と部分的なスカラー状態をパーサーオブジェクト内に保持します。後続のチャンクがすべての後続バイトを提供して初めて文字が完了します。remaining != 0 の状態でのストリーム終了は、依然として切り捨てエラーとなります。
なぜ正規表現だけを使用しないのですか？
正規表現でも一部のプレフィックスルールを表現できますが、チャンク境界、エラーインデックス、スカラー値の制約を扱うには状態マシンの方が明確です。カウンタは任意の長さの入力に対して一定の空間を使用し、厳格な検証へと自然に拡張できます。
過長エンコーディングを拒否するにはどうすればよいですか？
先頭バイトからシーケンス長と蓄積値を記録し、その値がその長さの最小範囲を満たしていることを要求します。また、0xD800..0xDFFF および 0x10FFFF を超える値も拒否します。
悪意のある極端に大きな入力を処理するにはどうすればよいですか？
呼び出し側がバイト制限、タイムアウト、およびエラーサンプリングポリシーを設定できるようにします。パーサー自体は O(1) の状態を保持し、最初の確定的なエラーでショートサーキットするため、不正な入力に対して追加のバッファを必要としません。