leetcode 125e 验证回文串

Published on:
Tags: leetcode

题目描述#

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明： 本题中，我们将空字符串定义为有效的回文串。

示例 1:

1
2
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

1
2
输入: "race a car"
输出: false

算法#

  1. 去除非字母、数字字符，大写字母转成小写字母，求出字符总长度
  2. 构造字符数组
  3. 验证

C代码#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
typedef int bool;


typedef struct node
{
    char data;
    struct node *next;
} strLink;

strLink * StrAssign(char *s);
bool isPalindrome(char * s);
void DispStr(strLink * s);
bool isPalindrome(char * s);
char GetChar(char c);
void StrCopy(strLink *str,int length,char *s);
void DispArr(char *arr,int length);

int main()
{
    char s[] = "";
    if(isPalindrome(&s[0]))
    {
        printf("true\t");
    }else
    {
        printf("false\t");
    }
    
    return 0;
}

char GetChar(char c)
{
    char res='\0';
    if((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') )
        res = c;
    
    if(c >= 'A' && c <= 'Z')
        res = c + 32;

    return res;
}

int StrLength(strLink *s)
{
    strLink * tmp = s->next;
    int i = 0;
    while(tmp != NULL)
    {
        i++;
        tmp = tmp->next;
    }
    return i;
}

strLink * StrAssign(char *s)
{
    strLink *tmp,*r,*p;
    tmp = (strLink *)malloc(sizeof(strLink));
    tmp->next = NULL;
    r = tmp;
    int i = 0;
    while(s[i] != '\0')
    {
        char res;
        if((res = GetChar(s[i])) == '\0')
        {
            i++;
            continue;
        }

        p = (strLink *)malloc(sizeof(strLink));
        p->data = res;
        r->next = p;
        r = p;
        i++;
    }
    r->next = NULL;
    return tmp;
}

void DispStr(strLink *s)
{
    strLink *tmp = s->next;
    while(tmp != NULL)
    {
        printf("%c",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}
void DispArr(char *arr,int length)
{
    for(int i=0;i<length;i++)
    {
        printf("%c\t",*(arr+i));
    }
    printf("\n");
}

void StrCopy(strLink *str,int length,char *s)
{
    int i = 0;
    strLink * tmp = str->next;
    while(tmp != NULL)
    {
        *(s+i) = tmp->data;
        i++;
        tmp = tmp->next;
    }
}

bool isPalindrome(char * s)
{
    //  求出长度
    strLink *str;
    str = StrAssign(s);
    // DispStr(str);
    int length = StrLength(str);
    if(length <= 1) return true;
    char strArr[length];

    //  构造字符数组
    StrCopy(str,length,&strArr[0]);
    // DispArr(&strArr[0],length);

    //  验证
    int i=0,j=length-1;
    while(i < j)
    {
        if(strArr[i] != strArr[j])
            return false;
        i++;
        j--;
    }
    return true;
}

时间复杂度#

算法的时间复杂度为 $O(n)$