第6章1文字列操作(有用なピンイン文字)

「パリンドロン」は、前に読んでも後ろに読んでも同じアルファベット順の単語や文です.
私たちは「回文」と呼んでいますが、代表的な文は「焼酎万瓶満住所」などです.
現在使用されているフィリンドロムは「Aman,a plan,a channel:Panama」です.
1.リストに変換

//문자열저장, 변환
class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
//펠린드롬 판별   
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
                
        return True

リストに変換する方法はstrsに文字を1つずつ格納し、isalnumは英語、数字を読み取り専用のコマンドです.また、大文字と小文字を区別するべきではないので、lowerを使用して小文字に変換します.
次に、次の値をリストに保存します.
['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']
popを使用して、保存したフィリンドロムを一番前の単語と一番後ろの単語と比較します.比較した単語がリストから漏れている.そして一番前と一番後ろの単語を比較します.
一番前の文字とpop()と一番後ろの単語をpop(0)で比較し、一致しない場合はfalseがtrueを返します.

この方法は運転時間が長いので、別の方法を試してみましょう.
2.データ・ウェアハウスによる最適化

class Solution:
    def isPalindrome(self, s: str) -> bool:
        #자료형 데크로 선언
        strs: Deque = collections.deque()
         
        #문자열 저장
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        #데크자료형 비교
        while len(strs) > 1:
            if strs.popleft() != strs.pop():
                return False
                        
        return True

popの演算は一方向である.これに対してDeckはHeadとTailの間で双方向演算を行うことができる.
strs: Deque = collections.Deque()のように、データ型をdeckと宣言するだけで、実行時間を大幅に短縮できます.

なぜならpop(0)はO(n)であり,Deckのpopleft()はO(1)であるからである.n回繰り返すごとにO(n二乗)とO(n)の差が大きい.この程度なら悪くない結果になるはずです.しかし、Pythonの最適化された内部機能を活用し、さらに性能を向上させる.
3.スライドの使用

import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        #정규식으로 불필요한 문자 필터링
        s = re.sub('[^a-z0-9]', '', s)
        
        return s == s[::-1] #슬라이싱

ここにはアルゴリズムがない.
PythonのSleeringを使用すると、不要な文字を通常フィルタリングして文字列を操作できます.
スライド:位置を指定すると、その位置の配列ポインタが取得され、そのポインタで接続されたオブジェクトが検索されて実際の""が検索されます.このプロセスは非常に高速です.
まず文字列をすべて小文字に変更します.
s = re.sub("^a-z 0-9",",s)はs=reという意味です.subのsubはsubtuteで、文字列を必要に変更する置換品の意味を持つ単語です.なんだ.[^a-z 0-9]の手前に^.では[^a-z 0-9]は[a-z 0-9]ではありません.
[a-z 0-9]でない場合は「空白」(削除)に変更します.
これらの変更をs=s[:-1]と比較するには、ホイールを使用します.trueまたはfalseを返します.

遅延は速いが,スライドを用いてより速い結果を示した.
前の解答はisalnumを用いてすべての文字を一つ一つチェックしたが,ここでは文字列全体を正規の方法で処理し,アルファベット数字のみをフィルタリングした.Pythonは、文字列を平らにしたりリストのように自由にスライドさせたり、[:-1]を使って反転したりする機能を提供しています.
番外c実施

bool isPalindrome(char * s){
    int bias_left = 0;
    int bias_right = 1;
    
    int str_len = strlen(s);
    for(int i = 0; i < str_len; i++) {
        //스킵 포인터 처리
        while (!isalnum(s[i + bias_left])) {
            bias_left++;
            if (i + bias_left == str_len)
                return true;
        }
        
        while (!isalnum(s[str_len - i - bias_right])) {
            bias_right++;
        }
        
        if (i + bias_left >= str_len - i -bias_right)
            break;
        
        //팰린드롬 비교
        if (tolower(s[i + bias_left]) !=  tolower(s[str_len - i - bias_right]))
            return false;
    }
    return true;
}

最高の速度を達成するために、c言語で実現しました.文字列を格納するcharポインタを直接操作し、できるだけ速く動作させます.
int str_len = strlen(s);
for(int i = 0; i < str_len; i++) {
//スキップポインタの扱い
while (!isalnum(s[i + bias_left])) {
bias_left++;
if (i + bias_left == str_len)
return true;
}
文字列が増えるにつれてbiase leftが文字列の長さに達するとtrueが返され、次に見るコードも一緒に見られます.
while (!isalnum(s[str_len - i - bias_right])) {
bias_right++;
右側から行い、文字列や数字でなければ追加スキップを表します.
if (i + bias_left >= str_len - i -bias_right)
break;
左側で行い、右側でも行い、I+biose leftが大きくなると止まります.
//法林症候群比較
if (tolower(s[i + bias_left]) != tolower(s[str_len - i - bias_right]))
return false;
そして最後にファリンドロンの左と右を比較し,異なる場合falseであればtrueを返して終了する.

すべての機能は直接処理する必要があり、コードが長くなりますが、位置ポインタを直接操作するため、速度が非常に速いです.
実行すると4 msの非常に速い速度が表示されます.