とりあえず総当たりで
最初、効率的な方法が思いつかなかったので、とりあえず全てのsubstrのパターンをチェックする方法(O(n^2))です。
class Solution {
public:
string longestPalindrome(string s) {
std::string longest;
const size_t size = s.size();
for (size_t begin_pos = 0; begin_pos < size; begin_pos++) {
for (size_t length = 1; begin_pos + length <= size; length++) {
const std::string sub_str = s.substr(begin_pos, length);
if (isPalindromic(sub_str) && longest.size() < sub_str.size()) {
longest = sub_str;
}
}
}
return longest;
}
private:
static bool isPalindromic(const std::string& src) {
std::string reversal = src;
std::reverse(reversal.begin(), reversal.end());
return src == reversal;
}
};もちろんコストが掛かるので、LeetCodeが許してくれるはずがありません。
タイムアウトになります。
両サイドの文字をチェックする方法
Discussionを見て参考にし、両サイドの文字が一致するかを見ていく方法で実装してみました。
class Solution {
public:
string longestPalindrome(string s) {
std::string longest = s.substr(0, 1); // ①
const size_t size = s.size();
for (size_t i = 0; i < size; i++) {
// ②
// ex) "aba"
for (size_t width = 1; 0 <= static_cast<int>(i-width) && i+width < size; width++) {
if (s[i-width] != s[i+width]) {
break;
}
const size_t length = width*2 + 1;
if (longest.size() < length) {
longest = s.substr(i-width, length);
}
}
// ③
// ex) "abba"
for (size_t width = 1; 0 <= static_cast<int>(i+1-width) && i+width < size; width++) {
if (s[i+1-width] != s[i+width]) {
break;
}
const size_t length = width*2;
if (longest.size() < length) {
longest = s.substr(i+1-width, length);
}
}
}
return longest;
}
};ざっと説明すると、
- “abc” が渡された際は任意の文字を返さないといけないのと、②と③では条件に一致しないため、先頭の文字で初期化する
- 奇数のsubstrを想定し、真ん中の文字から同じ距離離れた文字が一致するかを見ていく
- 偶数のsubstrを想定し、同じ距離離れた文字を比較していく
これで計算量は最短で線形時間(O(N))になりました。
ちなみに、unsigned 型同士(size_t)で計算すると結果も unsigned で出てくるので、for 分の条件については明示的にキャストが必要です。
-1 で抜けてほしいところが、キャストしないと unsigned int max と比較されてしまうので、条件がtrueとなり、string要素への不正アクセスが発生します。
以上です！