专栏首页米扑专栏【leetcode】Valid Palindrome

【leetcode】Valid Palindrome

Question:

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.

Anwser 1:

class Solution {
public:
    bool isStr(char &ch){
        if(ch >= '0' && ch <= '9'){
            return true;
        } else if(ch >= 'a' && ch <= 'z'){
            return true;
        } else if(ch >= 'A' && ch <= 'Z'){
           ch += 32;
           return true;
        } 
        
        return false;
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = s.length();
        if(len == 0){
            return true;
        }
        
        string str = "";
        for(int i = 0; i < len; i++){   // remove illegal char, such as "?" "/" ...
            if(isStr(s[i])){
                str += s[i];
            }
        }
        
        len = str.length();
        int mid = (len + 1) / 2;
        for(int i = 0; i < mid; i++){
            if(str[i] != str[len - 1 - i]){     // check front and end char
                return false;
            }
        }
        return true;
    }
};

Anwser 2:

class Solution {
public:
    bool isStr(char &ch){
        if(ch >= '0' && ch <= '9'){
            return true;
        } else if(ch >= 'a' && ch <= 'z'){
            return true;
        } else if(ch >= 'A' && ch <= 'Z'){
           ch += 32;
           return true;
        } 
        
        return false;
    }
    
    bool isPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int len = s.length();
        if(len == 0){
            return true;
        }
        
        int i = 0;
        int j = len - 1;
        while(i < j){
            if(!isStr(s[i])) {
                i++;
            } else if(!isStr(s[j])) {
                j--;
            } else if(s[i++] != s[j--]) {
                return false;
            }
        }
        
        return true;
    }
};

注意点:

1) 字母数字判断,注意字母中的字母大小写转换(把大写加32全部转化成小写)

2) 方法2中采用判断删除的方法,效率要高,且不占用另外字符串存储(str)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode】Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

    阳光岛主
  • 【leetcode】Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a pa...

    阳光岛主
  • 【leetcode】Two Sum

    Given an array of integers, find two numbers such that they add up to a specific...

    阳光岛主
  • [随缘一题]有效的三角形

    呼延十
  • Nebula3的Input系统

    逍遥剑客
  • 跨服夺矿战——java游戏服务器功能

    以前开发的游戏活动,在普通的游戏活动上添加了跨服玩法,需要用到世界服务器中转,提供思路给大家参考

    深雾
  • socket编程--相关函数--sendto();read();

    {1} 头文件:#include <sys/types.h> #include <sys/socket.h> 定义函数:int sendto(int s,...

    jianghaibobo
  • Student Attendance Record I

    Tyan
  • PHP实现网络刷投票

    PHP刷投票,让你高居榜首! 案例为一个半月以前。没有及时放出原因有二,一是因为博客域名备案没有下来,没有心情写东西。二是最主要的,及时放出对案例网站有严重的损...

    wangxl
  • Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】

    校门外的树 描述 校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券