leetcode Valid Palindrome C+&python問題解

タイトルの説明
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example, “A man, a plan, a canal: Panama” is a palindrome. “race a car” is not a palindrome.
Note: Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
文字列を指定して、文列であるかどうかを判断します.注意:この問題のデフォルトの空白列は文列です.
構想分析
まずc++コードの考え方を示し,大文字と小文字の問題があるため,すべてのアルファベットを小文字または大文字に統一する必要があるため,ここではSTLにおけるtransform()法を用いた.
コンテナ要素の変換操作に用いられるtransform()の使い方を簡単に記録します.次の2つの使用プロトタイプがあります.一方、反復器区間[first,last)の要素は、一元関数オブジェクトop操作を実行し、交換後の結果を[result,result+(last-first))区間に置く.他方、反復器区間[first 1,last 1)の要素*iは、[first 2,first 2+(last-first))の要素*jの順に、二元関数操作binary_op(*i,*j)を実行する
関数プロトタイプ

template < class InputIterator, class OutputIterator, class UnaryOperator >
  OutputIterator transform ( InputIterator first1, InputIterator last1,
                             OutputIterator result, UnaryOperator op );

template < class InputIterator1, class InputIterator2,
 class OutputIterator, class BinaryOperator > OutputIterator transform ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator binary_op );

パラメータの説明:
IRst 1,last 1は、要素変換を行う最初の反復器区間を示す[first 1,last 1].first 2は、要素変換を行う2番目の反復器区間の最初の要素の反復器位置を示す.この区間の要素個数は、最初の区間と等しい.
resultは、変換後の結果が格納される反復器区間の最初の要素の反復器位置opをパラメータとして一元関数オブジェクトopを用い、実行後に結果値を返すことを示す.関数またはオブジェクト内のクラスリロードoperator()であってもよい.binary_op用二元関数オブジェクトbinary_opはパラメータとして実行され、その後結果値が返される.関数またはオブジェクト内のクラスリロードoperator()であってもよい.
サンプルコードを指定

// transform algorithm example
#include <iostream> // std::cout
#include <algorithm> // std::transform
#include <vector> // std::vector
#include <functional> // std::plus

int op_increase (int i) { return ++i; }

int main () {
  std::vector<int> foo;
  std::vector<int> bar;

  // set some values:
  for (int i=1; i<6; i++)
    foo.push_back (i*10);                         // foo: 10 20 30 40 50

  bar.resize(foo.size());                         // allocate space

  std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);
                                                  // bar: 11 21 31 41 51

  // std::plus adds together its two arguments:
  std::transform (foo.begin(), foo.end(), bar.begin(), foo.begin(), std::plus<int>());
                                                  // foo: 21 41 61 81 101

  std::cout << "foo contains:";
  for (std::vector<int>::iterator it=foo.begin(); it!=foo.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '
';

  return 0;
}

output:
foo contains: 21 41 61 81 101
以下では、構想が大文字と小文字に統一された後、2つの反復器を利用して、1つは先頭を指し、1つは末尾を指し、毎回循環判断し、数字やアルファベットでなければスキップし、2つの反復器が指す内容が一致しなければ直接戻り、等しい場合は2つの反復器が同時に中間に1歩進み、2つのポインタが出会うまで文列であると判断する
コード実装を示します.

class Solution
{
public:
    bool isPalindrome(string s)
    {
        transform(s.begin(),s.end(),s.begin(),::tolower);
        string::iterator left=s.begin(),right=s.end();
        while(left<right)
        {
            if (!::isalnum(*left))
                left++;
            else if(!::isalnum(*right))
                right--;
            else if((*left)!=(*right))
                return false;
            else 
                {left++,right--;}

        }
        return true;
    }
};

ここでドメイン演算子に注意してください::の使用法は、c++ネーミングスペースの問題に関連し、ドメイン演算子を追加しないと、関数または変数のエラーが見つかりません.
python解法
この問題はpythonのリストジェネレータとリスト操作で簡潔に解決でき,まずリストジェネレータで数字とアルファベット以外の文字を削除して新しい文字列を得て,その列とその列の逆順序が等しいかどうかを直接判断すればよいという考え方である.
コード実装は次のとおりです.

class Solution:
    def isPalindrome(self, s):
        newS=[i.lower() for i in s if i.isalnum()]
        return newS==newS[::-1]