LeetCode 942. DI String Match
はじめに
LeetCode 「942. DI String Match」の問題をGoで解きました。
問題
問題文
A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:
・s[i] == 'I' if perm[i] < perm[i + 1], and
・s[i] == 'D' if perm[i] > perm[i + 1].
Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.
和訳
範囲[0, n]内のすべての整数のn + 1個の整数の順列permは、長さnの文字列sとして表すことができます。ここで
・perm[i] < perm[i + 1] の場合、s[i] == 'I'
・perm[i] > perm[i + 1] の場合、s[i] == 'D'
となります。
文字列sが与えられると、順列permを再構築して返します。有効な順列permが複数ある場合は、そのうちのいずれかを返します。
例
Input: s = "IDID"
Output: [0,4,1,3,2]
Input: s = "III"
Output: [0,1,2,3]
Input: s = "DDI"
Output: [3,2,0,1]
制約
- 1 <= s.length <= 105
- s[i] is either 'I' or 'D'.
解答1
この問題は、文字列sの各文字に対応するように順列permの要素の代償関係をうまく構築するのがポイントになります。
次のように整理して解きました。
- 'I' のとき：最小の数（
low）を使う →perm[i] < perm[i+1]が成り立つ - 'D' のとき：最大の数（
high）を使う →perm[i] > perm[i+1]が成り立つ
lowとhighの2つのポイントを持ち、左から順に数を割り当てていくことで、条件を満たす順列が構築できます。
最後にlowとhighは同じ帯になるので、それを最後の要素に入れます。
コード
func diStringMatch(s string) []int {
n := len(s)
result := make([]int, n+1)
low, high := 0, n
for i, c := range s {
if c == 'I' {
result[i] = low
low++
} else {
result[i] = high
high--
}
}
result[n] = low // low == high
return result
}
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(n)
Discussion