Fork me on GitHub

leetcode之125. 验证回文串

发表于 | 分类于
字数统计 437 字 | 阅读时长 2 分钟

题目描述：

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

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

示例 1:

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

示例 2:

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

解题思路一：

时间复杂度：$O(n)$,空间复杂度：$O(n)$.

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
class Solution {
public:
    bool isPalindrome(string s) {
        string ss = "";
        
        if(s.length() == 0) return true;
        
        //把s字符串转化ss（大写变小写，小写不变，标点符号、空格去掉）
        for(int n = 0; n < s.length(); n++)
        {
            if(s[n] >= 65 && s[n] <= 90)
            {
                s[n] = s[n] + 32;  
            }
            
            if(s[n] >= 97 && s[n] <=122 || s[n] >= 48 && s[n] <= 57)
            {
                 ss += s[n];
            }    
        
        }
        if(ss.length() <= 1 && ss.length() >= 0)  return true;
        
        for( int i = 0; i < ss.length() / 2; i++)
        {
            if(ss[i] != ss[ss.length() - i - 1])
               return false;
            
        }
        
        return true;
    }
};

解题思路二：

时间复杂度：$O(n)$,空间复杂度：$O(n)$.

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
class Solution {
public:
bool isPalindrome(string s) 
{
	int s_len = s.length();
	string s_t = "";
	if(s_len <= 1) return true;
	int i = 0;
	while(i < s_len)
	{
		if((s[i] >='0' && s[i] <= '9') || (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
		{
			s_t += s[i];
		}
		i++;
	}
	int s_t_len = s_t.length();
	//第一个和第二个分别是字符串的起始和结束的位置，第三个是字符串是起始操作位置，最后一个是操作，是转成大写还是转成小写
	transform(s_t.begin(),s_t.end(),s_t.begin(),::tolower); 
	cout << "s temp is " << s_t << endl;
	for(int j = 0; j < s_t_len / 2;j++)
	{
		if(s_t[j] != s_t[s_t_len - 1 - j]) return false;
	}
	return true;
}
};