LeetCode 2108. Find First Palindromic String in the Array
はじめに
LeetCode 「2108. Find First Palindromic String in the Array」の問題をGoで解きました。
問題
問題文
Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".
A string is palindromic if it reads the same forward and backward.
和訳
文字列の配列 words が与えられた場合、その配列の最初の回文の文字列を返す。そのような文字列がない場合は、空の文字列 "" を返す。
文字列が回文であるのは、前後に同じ読み方をする場合である。
例
Input: words = ["abc","car","ada","racecar","cool"]
Output: "ada"
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.
Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".
Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.
制約
- 1 <= words.length <= 100
- 1 <= words[i].length <= 100
- words[i] consists only of lowercase English letters.
解答1（Two Pointers）
今回の問題では、文字列が回文かどうかを判定する処理が必要となります。
回文かどうかの判定は、文字列の先頭・末尾から中央に向かって1文字ずつ文字を比較していくことで実現できます。
Two Pointers パターンが使えそうです。
Two Pointers パターン
Two Pointers は、2つの異なる位置からポインタを動かしながら探索を行う方法です。
主に配列や文字列操作を効率化するために使われ、時間計算量をO(n)に抑えることができるのがメリットです。
回文判定では 1回のループで 2文字をチェックできるため、対称性を活かして無駄な計算を減らせます。
コード
func firstPalindrome(words []string) string {
for _, word := range words {
if isPalindromic(word) {
return word
}
}
return ""
}
// 文字列が回文かどうかを判定する
func isPalindromic(s string) bool {
left, right := 0, len(s)-1
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
isPalindromicで、leftは左から探索を行うポインタ、rightは右から探索を行うポインタです。
ポインタを動かしながら両端から1文字ずつ比較していき、ループを抜けた場合にtrueを返しています。
計算量
- 時間的計算量： O(n * m)
-
mはwordの長さ、nはwordsの長さ
-
- 空間的計算量： O(1)
解答2（reverse を使う方法）
最適解ではないものの、別のアプローチもあるので紹介します。
文字列を反転させる処理を作り、文字列が回文かどうかを判定する方法です。
コード
func firstPalindrome(words []string) string {
for _, word := range words {
if word == reverse(word) {
return word
}
}
return ""
}
// 文字列を反転させる（ASCII のみなので `[]byte` を使用）
// Unicode 文字（漢字・絵文字など）が含まれる場合は `[]rune` を使う
func reverse(s string) string {
arr := []byte(s)
left, right := 0, len(arr)-1
for left < right {
arr[left], arr[right] = arr[right], arr[left]
left++
right--
}
return string(arr)
}
計算量
- 時間的計算量： O(n * m)
-
mはwordの長さ、nはwordsの長さ
-
- 空間的計算量： O(m)
reverseを使う方法では、新しいスライスを作成して文字列を逆順に格納するため、追加のメモリが必要となります。
そのため、メモリ効率を考えるなら Two Pointers の方法の方が良い選択肢になります。
参考
Two Pointers パターンを使用する別の問題を以下の記事で紹介しています。
Discussion