はじめに

ちょっとややこしい問題でした。英小文字からなる文字列と全アルファベットごとの距離を表した配列が与えられ、文字列に登場するアルファベットが距離配列に示される距離を守っているかを調べる問題。 たとえば abba と [2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] が与えられたとき、a は 距離 2 なので、距離を守っています。 b についても、その距離は 0 なので、距離を守っています。よってこの入力に対して true を返します。 なお、英小文字については「必ず 2 つのみ存在する」ことが約束されています。

考え方は、文字列を一つずつループしながら「本当に示された距離に次の英小文字が現れるか」を調べるというものです。 next というのは、距離の配列に与えられた距離に基づき、現在の文字が次に登場するインデックスを示す変数です。 確かに next の位置に同じ文字があれば OK、もしなければ、その時点で NG です。

少しはまったのが、単純にループを回すと、2回目に登場する文字についても同じ条件判定をしてしまう点です。つまり、2回目の a について同じ検査をすると、3回目が存在しないことが約束されているため、必ず false を返してしまいます。 このため、seen という map を用意し、過去にすでに見た文字であればスキップするようにしています。

この解法で Beats 100% です。エレガントではない気がしますね。

https://leetcode.com/problems/check-distances-between-same-letters/submissions/1624032889

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func checkDistances(s string, distance []int) bool {
    seen := make(map[byte]bool, 26)
    for i, c := range []byte(s) {
        if seen[c] {
            continue
        }
        next := i + distance[c - 'a'] + 1
        if next >= len(s) || s[next] != c {
            return false
        }
        seen[c] = true
    }
    return true
}

改善版

初手で考えていた方法が洗練されたのがこの改善版なんですが、“今見ている英小文字は2回目のものだ” という判定をする seen が少しコードを複雑にしており、それを無くしたものです。 最初は distance[i] に距離をマイナスにしたものを代入していけばいいと思ったんですが、distance[c - 'a'] = -1 とすることで、2回目はその文字自身を参照し、一致するので OK ですね。 もちろん、愚直に distance[c - 'a'] = -d - 2 としても pass します。 でも、単に -1 とあった方がシンプルでいいです。個人的に。

https://leetcode.com/problems/check-distances-between-same-letters/submissions/1624042985

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func checkDistances(s string, distance []int) bool {
    for i, c := range []byte(s) {
        d := distance[c - 'a']
        next := i + d + 1
        if  next >= len(s) || s[next] != c {
            return false
        }
        distance[c - 'a'] = -1
    }
    return true
}