Проверка на палиндром

В основном я задаюсь вопросом, есть ли что-то, что можно улучшить в этом коде на C ++:

#include <cstddef>
#include <string>

bool is_palindromic(std::string s)
{
    std::size_t i = 0;
    std::size_t j = s.length() - 1;
    while (i < j) {
        if (s[i++] != s[j--]) {
            return false;
        }
    }
    return true;
}
11 голосов | спросил Rohan James 20 32013vEurope/Moscow11bEurope/MoscowWed, 20 Nov 2013 21:02:20 +0400 2013, 21:02:20

4 ответа


11

Я хотел предложить отличный угол. Этот код может быть более общим. Почему он привязан к точно std::string - что, если мне нужно проверить палиндромный характер std::wstring или содержимое std::vector<T>? Как насчет std::list<T> или std::map<T> (если палиндромный может даже означать что-либо на std::map)? Вот как вы можете обрабатывать все те, у кого есть одна функция:

template <typename Sequence>
bool is_palindromic(const Sequence& seq)
{
    auto count = seq.size() / 2; // rounded down is fine, as a middle element matches itself
    auto i = seq.begin();        // prefer std::begin(seq) in C++14
    auto j = seq.rbegin();       // prefer std::rbegin(seq) in C++14

    for (Sequence::size_type c = 0; c < count; ++c, ++i, ++j)
    {
        if (*i != *j)
            return false;
    }
    return true; // considers sequences without mismatched characters to be palindromes
}

Обратите внимание, что я добавил другие комментарии, с которыми я согласен, в частности, передавая константу ссылки и используя последовательность size_type. Однако я не уверен, как лучше всего поддерживать массивы; в то время как std::[r]begin будет обрабатывать массивы, я не считаю, что массивы имеют .size() или ::size_type. Я предполагаю, что это означает, что им нужна их перегрузка или, по крайней мере, некоторые перегруженные помощники.

ответил Michael Urman 20 32013vEurope/Moscow11bEurope/MoscowWed, 20 Nov 2013 22:42:39 +0400 2013, 22:42:39
7

Прежде всего, вы должны передать std::string по ссылке const, а не по значению, поэтому замените std::string s по const std::string& s, иначе вы сделаете целую копию строки каждый раз, когда вы вызываете функцию.

Кроме того, программа может сбой, если код std::string пуст, так как вы выполняете std::size_t j = s.length() - 1;. Если s.length() == 0, j, вероятно, будет большое количество, и вы закончите с segfault из-за индекса вне диапазона.

Как было предложено Loki в комментариях, вы также можете использовать цикл for вместо while, чтобы ваш код выглядел более чистым.

Еще одно предложение Jamal: использование std::string::size_type вместо std::size_t (и удалив #include <cstddef>) будет более идиоматично. Тип, возвращаемый std::string::length, не требуется std::size_t, но std::string::size_type.

Поэтому я бы переписал его как:

bool is_palindromic(const std::string& s)
{
    if (s.empty())
    {
        // You can return true if you think that
        // an empty string is a palyndrome
        return false;
    }
    for (std::string::size_type i=0, j=s.length()-1
         ; i < j ; ++i, --j)
    {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}
ответил Morwenn 20 32013vEurope/Moscow11bEurope/MoscowWed, 20 Nov 2013 21:23:19 +0400 2013, 21:23:19
7

Я просто хотел прослушивать «ленивый» (если не исполнительный) способ сделать это, используя обратные итераторы:

bool is_palindrome(const std::string& s)
{
    return s == std::string(s.rbegin(), s.rend());
}

Это очень просто и очень читаемо. Вы можете развернуть это, чтобы сделать что-то вроде удаления пунктуации, если хотите, но это немного сложнее (хотя оно все еще короткое):

// Note that the pass by value is intentional here, so we don't modify
// the original string when using std::remove_if
bool is_palindrome(std::string s)
{
    auto it = std::remove_if(s.begin(), s.end(), [](char c) { return !std::isalpha(c); });
    return std::equal(s.begin(), it, std::reverse_iterator<std::string::iterator>(it));
}

Это также можно превратить в шаблон, который будет работать с любой последовательностью с минимальными усилиями.

ответил Yuushi 22 52013vEurope/Moscow11bEurope/MoscowFri, 22 Nov 2013 10:06:46 +0400 2013, 10:06:46
4

Поиск чего-то как симметричного как сами палиндромы, я пришел к этому довольно живописному решению, которое не обрабатывает пустую строку определенным образом, а как палиндромическое:

#include <string>

bool is_palindromic(const std::string& s)
{
    std::string::const_iterator start = s.begin();
    std::string::const_iterator end = s.end();
    while (start < end) {
        if (*(start++) != *(--end)) {
            return false;
        }
    }
    return true;
}

Его главный недостаток - это избыточная проверка на самоопределение центрального символа.

ответил Wolf 26 22013vEurope/Moscow11bEurope/MoscowTue, 26 Nov 2013 18:58:38 +0400 2013, 18:58:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132