Pythonで解く単一列キーボード問題：タイピングにかかる時間の計算方法

問題の概要

すべてのキーが1列に並んだ特殊なキーボードを想像してください。キーボードのレイアウトは、長さ26の文字列(インデックスは0から25)で表され、最初は指がインデックス0の位置にあるものとします。文字を入力するには、次に入力したい文字のインデックスまで指を移動させる必要があります。このとき、インデックスiからjへ指を移動するのにかかる時間は|i − j|で表されます。

そこで、指定された文字列を1本の指で入力するのにかかる合計時間を求める関数を定義します。例えば、キーボードのレイアウトが「abcdefghijklmnopqrstuvwxyz」で、入力したい単語が「hello」の場合、出力は20になります。aからhまでは7、hからeまでは3、eからlまでは7、lからlまでは0、lからoまでは3であるため、合計は7 + 3 + 7 + 0 + 3 = 20となるからです。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 辞書(マップ)dを作成し、変数zを0で初期化します。
• iを0からキーボードレイアウト文字列kの長さまでループします。
  • d[k[i]] := i として、各文字のインデックスを記録します。
• ans := 0 で初期化します。
• word内の各文字iに対して以下を実行します。
  • ans := ans + |d[i] − z|
  • z := d[i](指の現在位置を更新)
• 最後にansを返します。

アルゴリズムのポイント

まずキーボード上の各文字の位置を辞書に事前に記録しておくことで、任意の文字への移動距離をO(1)で参照できるようになります。その後は、入力したい単語の各文字について、前回の指の位置との絶対差を累積していくだけで答えが求まります。時間計算量はO(n)(nは単語の長さ)、空間計算量はO(1)(キーボードは固定長26文字)と非常に効率的です。

実装例(Python)

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

class Solution(object):
    def calculateTime(self, k, w):
        d = {}
        z = 0
        for i in range(len(k)):
            d[k[i]] = i
        ans = 0
        for i in w:
            ans += abs(d[i] - z)
            z = d[i]
        return ans
ob1 = Solution()
print(ob1.calculateTime("abcdefghijklmnopqrstuvwxyz", "hello"))

入力

"abcdefghijklmnopqrstuvwxyz"
"hello"

出力

20