Pythonで左端または右端の位置に到達できるかどうかを確認するプログラム

問題の概要

R、B、ドット(.) の3種類の文字を含む文字列を考えてみましょう。R は現在位置、B は移動が妨げられている(ブロックされた)位置、ドット(.) は空いている位置を表します。1ステップごとに、現在位置から有効な(空いている)隣接する位置へ移動することができます。このとき、文字列の左端または右端の位置に到達できるかどうかを判定する必要があります。

例えば、入力が s = "...........R.....BBBB....." の場合、出力は True になります。これは、R の左側にブロック(B)がひとつも存在しないため、R は左端の位置に到達できるからです。

解決のアプローチ

この問題を解くには、以下の手順に従います。

• r_pos := 文字列 s 内の 'R' のインデックス位置
• s の先頭から r_pos - 1 までの範囲に 'B' が存在しない、または r_pos から末尾までの範囲に 'B' が存在しない場合に True を返す

つまり、「R より左側にブロックがない」または「R から右側にブロックがない」のどちらかが成立すれば、対応する方向の端に到達できるということです。

理解を深めるために、以下の実装例を見てみましょう。

実装例(Python)

class Solution:
    def solve(self, s):
        r_pos = s.find('R')
    return not 'B' in s[:r_pos] or not 'B' in s[r_pos:]

ob = Solution()
s = "...........R.....BBBB....."
print(ob.solve(s))

入力

"...........R.....BBBB....."

出力

True

コードの解説

まず、s.find('R') を使って文字列内の R の位置を取得します。次に、スライス s[:r_pos](R より左側の部分)と s[r_pos:](R を含む右側の部分)のそれぞれに 'B' が含まれているかを確認します。どちらか一方でも 'B' が含まれていなければ、その方向の端には何も障害物がないため True を返します。

このアルゴリズムの計算量は O(n)(n は文字列の長さ)であり、文字列を数回走査するだけなので非常に効率的です。追加のメモリもほとんど不要で、シンプルかつ実用的な解法と言えます。