Pythonで解く「1ビット文字と2ビット文字」の判定問題|アルゴリズムと実装例

問題の概要

ここでは、2種類の特殊な文字を扱います。1つ目の文字は1ビットの「0」で表現され、2つ目の文字は2ビットの「10」または「11」で表現されます。複数のビットから構成される文字列が与えられたとき、その最後の文字が必ず1ビット文字になるかどうかを判定するのが課題です。なお、与えられるビット列は必ず0で終わることが保証されています。

入力例と出力例

たとえば、入力が [1,0,0] の場合、出力は True になります。これは、このビット列をデコードできる方法が「2ビット文字(10)」と「1ビット文字(0)」の組み合わせしか存在しないためです。したがって、最後の文字は1ビット文字であると結論付けられます。

解法のアプローチ

この問題は、ビット列を先頭から順に走査するシミュレーションによって解決できます。具体的には、以下の手順に従います。

• bits の長さが 1 より大きい間、次の処理を繰り返す
• 変数 current に bits の先頭要素を代入し、その要素をリストから削除する
• current が 1 だった場合は、2ビット文字として読み進めたことになるため、さらに bits の先頭要素を1つ削除する
• ループ終了後、bits の長さが 0 になっていれば False を返す
• それ以外の場合は、bits[0] が 0 であれば True、そうでなければ False を返す

この方法のポイントは、「1」が出てきたら必ず直後の1ビットもセットで消費するという点です。これにより、最後に残った1ビットが独立した1ビット文字(0)なのかどうかを正確に判定できます。

処理の流れ(入力 [1,0,0] の場合)

1. 初期状態:bits = [1, 0, 0](長さ3)
2. 1回目のループ:先頭の「1」を取り出し、2ビット文字と判断して次の「0」も削除 → bits = [0]
3. 残りの長さが1になったため、ループを終了
4. bits[0] が 0 なので True を返す

実装例

それでは、実際のコードを見て理解を深めましょう。

class Solution:
   def isOneBitCharacter(self, bits):
      while len(bits) > 1:
         current = bits.pop(0)
         if current == 1:
            bits.pop(0)
      if len(bits) == 0:
         return False
      return bits[0] == 0
ob = Solution()
print(ob.isOneBitCharacter([1,0,0]))

入力

[1,0,0]

出力

True

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。ただし、Pythonの list.pop(0) は先頭要素の削除に O(n) のコストがかかるため、大規模な入力を扱う場合は、インデックスを用いて走査位置を管理する方式に置き換えることで、より効率的な実装になります。