首页 > 代码库 > HappyLeetcode2: Valid Palindrome

HappyLeetcode2: Valid Palindrome

题目

 

解题步骤

  1. 对字符串进行处理,字符小写,去掉多余标点。
  2. 对空字符串的情况进行判断。
  3. 建立一个新的字符串对象,存入原字符串翻转后的结果
  4. 如果这两个字符串相等,那么返回True,否则,返回False。

我的答案

第1版:

class Solution:

    # @param s, a string

    # @return a boolean

    def isPalindrome(self, s):

        s=s.strip()

        s=s.lower()

        eff=‘qwertyuiopasdfghjklzxcvbnm1234567890‘

        s=[s.replace(cha,‘‘) for cha in s if not cha in eff]

        if s==‘‘:

            return True

        return s[:,len(s)/2]==s[(len(s)+1)/2,:][::-1]

 

放入测试中,结果发现耗时过多,在输入为””的时候完全通不过,目前不知道原因。

 

class Solution {

public:

    bool isPalindrome(string s) {

        string snew="";

        int i;

        for(i=0;i<s.size();++i){

            if(isalnum(s[i])){

                snew+=tolower(s[i]);

            }

        }

        for(i=0;i<=snew.size()/2;++i){

            if(snew[i] != snew[snew.size()-1-i])

                return false;

        }

        return true;

    }

};

这个C++版本的回答成功通过。

参考答案

参考答案1

class Solution:

    # @param s, a string

    # @return a boolean

    def isPalindrome(self, s):

        newS= [i.lower() for i in s if i.isalnum()]

        #return newS == newS[::-1]

        return newS[:len(newS)/2] == newS[(len(newS)+1)/2:][::-1] 

 

解析:

用到了两个我不熟悉的函数:i.isalnum():判断一个字符串或者一个字符是否为字母或者数字。这个非常好用。

对于最后一句话: newS[:len(newS)/2] == newS[(len(newS)+1)/2:][::-1]。如果涉及到列表长度的问题时,有时会考虑到列表长度为奇数和偶数的不同的情况。这句话对列表长度为奇数和偶数的都考虑过了,都符合要求。

参考答案2

python

class Solution:
    # @param s, a string
    # @return a boolean
    def isPalindrome(self, s):
        if s == ‘‘:
            return True
        else:
            sTmp = ‘‘
            for i in range(0, len(s)):
                if s[i] >= ‘a‘ and s[i] <= ‘z‘ or s[i] >= ‘0‘ and s[i] <= ‘9‘ or s[i] >= ‘A‘ and s[i] <= ‘Z‘:
                    sTmp += s[i]
            sTmp = sTmp.lower()
            for i in range(0, len(sTmp)/2):
                if sTmp[i] != sTmp[len(sTmp)-1-i]:
                    return False
            return True

C++

bool isPalindrome(string s) {

    if (!s.compare("")) return true;

 

    for (int i = 0, j = s.length() - 1; j >= 0 && i < s.length();) {

        if (!isalpha(s[i]) && !isdigit(s[i])) // if not alphabetic increment

            i++;

        else

        if (!isalpha(s[j]) && !isdigit(s[j])) // if not alphabetic increment

            j--;

        else {

            if (tolower(s[i]) != tolower(s[j]))

                return false;

            i++; j--;

        }

    }

    return true;

}

解析:

加粗的部分好好领会一下。

我的思路是,新建一个新的字符串,存储起来。

后来看过一些参考答案,发现其实没有必要建立一个新的字符串。直接在原有字符串上进行判断就行了,当然,这种方案在后来也有一定的复杂度。尝试着学习一下。

经验教训:

对于字符串的使用和操作还是严重不熟啊。

收获学到的东西

函数:

isalnum():这个函数在C++ 和 python之中都有,直接用来判断是否是字符或者数字。

tolower():将大写字母转换为小写字母。同样的函数还有toupper():功能不言而喻。

 

HappyLeetcode2: Valid Palindrome