🖋
LeetCode 557. Reverse Words in a String III
はじめに
LeetCode 「557. Reverse Words in a String III」の問題をGoで解きました。
問題
問題文
Given a string s, reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
和訳
文字列 s が与えられた場合、空白と最初の語順を維持しながら、文内の各単語の文字の順序を逆にします。
例
Input: s = "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Input: s = "Mr Ding"
Output: "rM gniD"
制約
- 1 <= s.length <= 5 * 104
- s contains printable ASCII characters.
- s does not contain any leading or trailing spaces.
- There is at least one word in s.
- All the words in s are separated by a single space.
解答
各単語の文字を反転させる処理は Two Pointers パターン で実現できます。
Two Pointers パターン の問題は以下の記事でも解説していますので、参考にしてください。
その上で、追加のメモリを使用しないように、インプレースで変換できないか考えました。
空白が単語と単語の境になるので、空白の前の文字が単語の終わり、空白の次の文字が単語の終わりと解釈できます。
文字列を線形に探索していき、空白を見つけたら その前の文字までを1単語として反転します。
ループの最後には、 最後の単語を反転する処理が別途必要になります。
コード
func reverseWords(s string) string {
arr := []byte(s)
wordStart := 0 // 各単語の開始インデックス
for i, v := range arr {
// 空白を見つけたら、その前までの単語を反転
if v == ' ' {
reverse(arr[wordStart:i])
wordStart = i + 1 // 次の単語の開始位置を更新
}
}
// 最後の単語を反転
reverse(arr[wordStart:])
return string(arr)
}
func reverse(arr []byte) {
left, right := 0, len(arr)-1
for left < right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
}
leftは単語の先端を示しています。
reverse関数では、スライスの一部を渡して反転処理をしています。
Goのスライスは内部にポインタを持つデータ構造なので、スライスの一部を渡しても元の配列を参照しており、変更が反映されます。
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(1)
参考
本文でも触れましたが、Two Pointers パターンを使用する別の問題を以下の記事で紹介しています。
Discussion