125_验证回文串

风扫地

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

1. int isNum(char ch)
   
2. {
   
3.     return ((ch >= '0') && (ch <= '9')) ? 1 : 0;
   
4. }
   
5. 
   
6. int isChar(char ch)
   
7. {
   
8.     return (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) ? 1 : 0;
   
9. }
   
10. 
    
11. bool isPalindrome(char * s)
    
12. {
    
13.    
    
14.     bool    ret_val = true          ; /* init */
    
15.     int     len     = strlen(s)     ;
    
16.     char*   head    = s             ;
    
17.     char*   tail    = &s[len-1]     ;
    
18.     char    ch_h    = 0             ;
    
19.     char    ch_t    = 0             ;
    
20.     int     type_h  = 0             ;
    
21.     int     type_t  = 0             ;
    
22.    
    
23.     while(head < tail)
    
24.     {
    
25.         
    
26.         ch_h    =   (*head)                         ;
    
27.         ch_t    =   (*tail)                         ;
    
28.         type_h  =   isNum(ch_h) + isChar(ch_h) * 2  ;
    
29.         type_t  =   isNum(ch_t) + isChar(ch_t) * 2  ;
    
30.         
    
31.         if(  (type_h != 0)
    
32.            &&(type_t != 0)
    
33.         )
    
34.         {
    
35.             if (type_h != type_t)
    
36.             {
    
37.                 ret_val = false;
    
38.                 break;
    
39.             }
    
40.             /* 这里可以省略
    
41.             else if(type_h==0x01)
    
42.             {
    
43.                 if(ch_h == ch_t)
    
44.                 {
    
45.                     head++;
    
46.                     tail--;
    
47.                     continue;
    
48.                 }
    
49.                 else
    
50.                 {
    
51.                     ret_val = false;
    
52.                     break;
    
53.                 }
    
54.                
    
55.             }*/
    
56.             else
    
57.             {
    
58.                 if((ch_h|32) == (ch_t|32))
    
59.                 {
    
60.                     head++;
    
61.                     tail--;
    
62.                     continue;
    
63.                 }
    
64.                 else
    
65.                 {
    
66.                     ret_val = false;
    
67.                     break;
    
68.                 }
    
69.             }
    
70.         }
    
71.         else if(type_h == 0)    /* head指向非需要比较类型*/
    
72.         {
    
73.             head++;
    
74.         }
    
75.         else if(type_t==0)  /* tail指向非需要比较类型*/
    
76.         {
    
77.             tail--;
    
78.         }
    
79.     }
    
80.    
    
81.    
    
82.     return ret_val;
    
83. 
    
84. }
    

复制代码

1. /*
   
2. 执行用时 :4 ms, 在所有C提交中击败了96.32%的用户
   
3. 内存消耗 :7.4 MB, 在所有C提交中击败了58.22%的用户
   
4. 
   
5. 476 / 476 个通过测试用例
   
6. 状态：通过
   
7. 执行用时：4 ms
   
8. 提交时间：0 分钟之前
   
9. */

复制代码

Nice.

风扫地

高级语言可以尝试

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

风扫地

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

1. int isNum(char ch)
   
2. {
   
3.     return ((ch >= '0') && (ch <= '9')) ? 1 : 0;
   
4. }
   
5. 
   
6. int isChar(char ch)
   
7. {
   
8.     return (((ch >= 'a') && (ch <= 'z')) || ((ch >= 'A') && (ch <= 'Z'))) ? 1 : 0;
   
9. }
   
10. 
    
11. bool isPalindrome(char * s)
    
12. {
    
13.    
    
14.     bool    ret_val     = true          ; /* init */
    
15.     int     valid_len   = 0             ;
    
16.     int     i           = 0             ;
    
17. 
    
18.     i         = 0;
    
19.     valid_len = 0;
    
20.     while(s[i] != '\0')
    
21.     {
    
22.         if(isNum(s[i]) || isChar(s[i]))
    
23.         {
    
24.             s[valid_len] = s[i] | 32;
    
25.             valid_len ++;
    
26.         }
    
27.         i++;
    
28.     }
    
29.    
    
30.     i = 0;
    
31.     while( i < valid_len-1 )
    
32.     {
    
33.         if(s[i] != s[valid_len-1])
    
34.         {
    
35.             ret_val = false;
    
36.             break;
    
37.         }
    
38.         i++;
    
39.         valid_len--;
    
40.     }
    
41. 
    
42.     return ret_val;
    
43. }

复制代码

1. 执行用时 :
   
2. 4 ms
   
3. , 在所有C提交中击败了
   
4. 96.32%
   
5. 的用户
   
6. 内存消耗 :
   
7. 7.5 MB
   
8. , 在所有C提交中击败了
   
9. 30.92%
   
10. 的用户

复制代码