Leetcode---Valid Palindrome

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.

这道题有很多种解法，比如先去掉冗余字符，然后判断一个干净的纯小写字符串；或者两个指针一前一后向中间遍历，遇到冗余字符跳过。。

判断一个纯小写字符串是否是回文也有不同的办法，比如前后两个指针往中间扫；或者找到中点往两边扩展；或者

可以利用回文的子结构性质，DP。公式就是

f(i,j)=f(i+1,j-1)&&s[i]==s[j], 0<=i

f(i,j)=true, i>=j

我们采用最简单的第一种方法，注意字符串长度为奇偶数时都可以用这段code来做：

for(int j=0;j<t.length()/2;j++){
            if(t[j]!=t[t.length()-1-j])
                return false;
        }
        return true;

代码如下：

bool isPalindrome(string s) {
        string t;
        for(int i=0;i<s.length();i++){
            if(s[i]>='a' && s[i]<='z'){
                t+=s[i];
            }
            else if(s[i]>='A' && s[i]<='Z'){
                t+=s[i]-'A'+'a';
            }
            else if(s[i]>='0' && s[i]<='9'){
                t+=s[i];
            }
        }
        for(int j=0;j<t.length()/2;j++){
            if(t[j]!=t[t.length()-1-j])
                return false;
        }
        return true;
    }

阅读(897) | 评论(0) | 转发(0) |

0

上一篇：Leetcode---Interleaving String

下一篇：Leetcode---Palindrome Number