论坛 › 数据结构与算法 › 125_验证回文串

风扫地 发表于 2019-6-17 15:51:19

125_验证回文串

/*
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
*/


int isNum(char ch)
{
    return ((ch >= '0') && (ch <= '9')) ? 1 : 0;
}

int isChar(char ch)
{
    return (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) ? 1 : 0;
}

bool isPalindrome(char * s)
{
   
    bool    ret_val = true          ; /* init */
    int   len   = strlen(s)   ;
    char*   head    = s             ;
    char*   tail    = &s   ;
    char    ch_h    = 0             ;
    char    ch_t    = 0             ;
    int   type_h= 0             ;
    int   type_t= 0             ;
   
    while(head < tail)
    {
      
      ch_h    =   (*head)                         ;
      ch_t    =   (*tail)                         ;
      type_h=   isNum(ch_h) + isChar(ch_h) * 2;
      type_t=   isNum(ch_t) + isChar(ch_t) * 2;
      
      if((type_h != 0)
         &&(type_t != 0)
      )
      {
            if (type_h != type_t)
            {
                ret_val = false;
                break;
            }
            /* 这里可以省略
            else if(type_h==0x01)
            {
                if(ch_h == ch_t)
                {
                  head++;
                  tail--;
                  continue;
                }
                else
                {
                  ret_val = false;
                  break;
                }
               
            }*/
            else
            {
                if((ch_h|32) == (ch_t|32))
                {
                  head++;
                  tail--;
                  continue;
                }
                else
                {
                  ret_val = false;
                  break;
                }
            }
      }
      else if(type_h == 0)    /* head指向非需要比较类型*/
      {
            head++;
      }
      else if(type_t==0)/* tail指向非需要比较类型*/
      {
            tail--;
      }
    }
   
   
    return ret_val;

}



/*
执行用时 :4 ms, 在所有C提交中击败了96.32%的用户
内存消耗 :7.4 MB, 在所有C提交中击败了58.22%的用户

476 / 476 个通过测试用例
状态：通过
执行用时：4 ms
提交时间：0 分钟之前
*/

Nice.

风扫地 发表于 2019-6-17 15:56:54

高级语言可以尝试

1.将不需要比较的元素进行remove 得到s1
2.字符串大写话或小写化 lower upper,得到s2
3.看 s2 == s2.reverse 的结果即可。

风扫地 发表于 2019-6-17 16:20:17

解法二：先筛选，再比较。
缺点： 会破坏s的原有数据。

int isNum(char ch)
{
    return ((ch >= '0') && (ch <= '9')) ? 1 : 0;
}

int isChar(char ch)
{
    return (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) ? 1 : 0;
}

bool isPalindrome(char * s)
{
   
    bool    ret_val   = true          ; /* init */
    int   valid_len   = 0             ;
    int   i         = 0             ;

    i         = 0;
    valid_len = 0;
    while(s != '\0')
    {
      if(isNum(s) || isChar(s))
      {
            s = s | 32;
            valid_len ++;
      }
      i++;
    }
   
    i = 0;
    while( i < valid_len-1 )
    {
      if(s != s)
      {
            ret_val = false;
            break;
      }
      i++;
      valid_len--;
    }

    return ret_val;
}


执行用时 :
4 ms
, 在所有C提交中击败了
96.32%
的用户
内存消耗 :
7.5 MB
, 在所有C提交中击败了
30.92%
的用户

查看完整版本: 125_验证回文串