首页 > 试题广场 >

判断回文串

[编程题]判断回文串

热度指数：30318 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

判断题目给出的字符串是不是回文，仅考虑字符串中的字母字符和数字字符，并且忽略大小写

例如："nowcoder Is Best tsebsi: redoc won"是回文

"race a car"不是回文

注意：

你有没有考虑过字符串可能为空？这是面试时应该提出的一个好问题。

针对这个问题，我们定义空字符串是回文

示例1

输入

"nowcoder Is Best tsebsi: redoc won"

输出

true

示例2

输入

"race a car"

输出

false

算法知识视频讲解

小刀初试

从两头扫描，遇到非字母数子的跳过。

bool isPalindrome(string s) {
        int i,j;
        for(i=0,j=s.length()-1;i<j;++i,--j){
            while(i<j && !isalnum(s[i])) ++i;
            while(i<j && !isalnum(s[j])) --j;
            if (i<j && tolower(s[i])!=tolower(s[j])) return false;
        }
        return true;
    }

发表于 2016-08-04 17:18:12 回复(7)

星x之火


public static boolean isPalindrome(String s) {
        if(s.isEmpty()) return true;
        String str = s.replaceAll("\\W", ""); // 使用正则去除非字符数字的字符
        str = str.toLowerCase(); 
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) != str.charAt(str.length() - i -1)) {
                return false;
            }
        }
        return true;
    }

编辑于 2018-01-17 15:47:54 回复(3)

HW柯可

//利用栈，入栈顺序和出栈顺序应一致
import java.util.*;
public class Solution {
    public boolean isPalindrome(String s) {
        Stack stack=new Stack();
        String s1=s.replaceAll("\\W","").toUpperCase();
        if(s1.isEmpty()||s1.length()==1)
            return true;
        for(int i=0;i<s1.length();i++){
            stack.push(s1.charAt(i));
        }
        for(int i=0;i<s1.length();i++){
            char c=(char)stack.pop();
            if(s1.charAt(i)!=c)
                return false;
            else if(i==s1.length()-1){
                return true;
            }
        }
        return false;
    }
}

发表于 2018-09-07 17:44:22 回复(0)

C/C++

F-L

class Solution {
public:
    bool isPalindrome(string s) {
        int len = s.length();
        int i = 0;
        int j = len-1;
        while(i < j){
            if(!isalnum(s[i])){
                ++i;
                continue;
            }
            
            if(!isalnum(s[j])){
                --j;
                continue;
            }
            
            if(tolower(s[i]) == tolower(s[j])){
                ++i;
                --j;
            }else{
                return false;
            }
        }
        return true;
    }
};

发表于 2018-04-02 11:34:07 回复(0)

张佃鹏

public class Solution {
    public boolean isPalindrome(String s) {
        s = s.toUpperCase();
        int i = 0, j = s.length() - 1;
        while(i < j){
            while((i < j) && !isalnum(s.charAt(i))) i++;
            while((i < j) && !isalnum(s.charAt(j))) j--;
            if(i <= j && s.charAt(i) == s.charAt(j)){
                i++;
                j--;
            }else{
                return false;
            }
        }
        return true;
    }
    
    public boolean isalnum(char c){
        return Character.isDigit(c) || Character.isLetter(c);
    }
}

发表于 2019-10-14 09:10:33 回复(0)

C/C++

牛客271007360号

bool isPalindrome(string s) {
transform(s.begin(),s.end(),s.begin(),::tolower);
vector<char> v;
for (int i = 0; i < s.length(); i++){
         if (s[i] >= 'a'&&s[i] <= 'z' || s[i] >= '0' && s[i] <= '9')
             v.push_back(s[i]);
     }
return string(v.begin(),v.end())==string(v.rbegin(),v.rend());
}

编辑于 2021-02-01 15:27:22 回复(0)

C/C++

沉默是金是我啊

//思路是把非数字和字母排除，最后判断是否回文
bool isPalindrome(string s) {
        // write code here
        if(s.length()==0)
            return true;
        // write code here
        for(int i=0;i<s.length();i++)
        {
            if('a'<=s[i]<='z'|| '0'<= s[i] <='9');
            else if('A' <= s[i] <= 'Z')
                 s[i] = s[i] + 32;
            else
                s.erase(s[i]);
        }
            return s==string(s.rbegin(),s.rend());
    
    }

我这个“a.”通不过，搞不太懂了。

发表于 2020-08-20 18:42:54 回复(0)

Java

金秋十月

public class Solution {
public boolean isPalindrome(String s) {
if(s.equals(""))return true;
int j = 0;
s = s.toUpperCase();
char []str = new char [s.length()];
for(int i = 0;i<s.length();i++){
if((s.charAt(i)>='A'&&s.charAt(i)<='Z')||(s.charAt(i)>='0'&&s.charAt(i)<='9')){
str[j++] = s.charAt(i);
}
}
for(int i = 0;i<j/2;i++){
if(str[i]!=str[j-i-1])
return false;
}
return true;
}
}
/*

运行时间：165ms

占用内存：16564k

发表于 2019-11-03 12:07:14 回复(0)

KIMVON_C

    public boolean isPalindrome(String s) {
        int start=0;
        int end = s.length()-1;
        while(start<=end){
            char p = s.charAt(start);
            char l = s.charAt(end);
            if (!isChar(p)){
                start++;
                continue;
            }
            if (!isChar(l)){
                end--;
                continue;
            }
            if (Character.toLowerCase(p)!=Character.toLowerCase(l)){
                return false;
            }
            start++;
            end--;
        }

        return true;
    }


    private boolean isChar(char c){
        if ((c>='0'&&c<='9')||(c>='a'&&c<='z')||(c>='A'&&c<='Z')){
            return true;
        }

        return false;
    }

发表于 2018-07-31 13:41:16 回复(1)

C/C++

蛟龙吐火球丰

class Solution {
public:    
    string fil(string s,int l)
    {
        string out="";
        for(int i=0;i<l;i++)
        {

            if(s[i]>='a'&&s[i]<='z')
                out+=s[i]-32;    
            else if((s[i]>='A'&&s[i]<='Z')||(s[i]>='0'&&s[i]<='9'))
                out+=s[i];
        }
        return out;
    }
    bool isPalindrome(string s) {

        int l=s.length();
        if(l==0)
            return false;
        if(l==1)
            return true;
        string s1=fil(s,l);
        l=s1.length();
        for(int i=0;i<l/2;i++)
        {
            if(s1[i]!=s1[l-1-i])
                return false;
        }
        return true;
    }
};

发表于 2018-06-05 08:33:43 回复(0)

神算皮卡

class Solution {
public:
    bool isPalindrome(string s) {
        if(s=="") return true;
        string tmp="",rev="";
        for(int i=0;i<s.length();i++)
            if('A'<=s[i]&&s[i]<='Z') tmp+=(char)(s[i]-'A'+'a');
            else if('a'<=s[i]&&s[i]<='z'||'0'<=s[i]&&s[i]<='9') tmp+=s[i];
        rev=tmp;
        reverse(rev.begin(),rev.end());
        return rev==tmp;
    }
};

发表于 2018-05-27 14:03:22 回复(0)

C/C++

nbgao

class Solution {
public:
    bool isPalindrome(string s) {
        int l = s.length();
        for(int i=0,j=l-1;i<j;i++,j--)
        {
            while(i<j && !isalnum(s[i]))
                i++;
            while(i<j && !isalnum(s[j]))
                j--;
            if(i<j && tolower(s[i]) != tolower(s[j]))
                return false;         }         return true;
    }
};

发表于 2017-09-26 00:58:01 回复(0)

wanlanwalan

/*
给定一个字符串，确定它是否是回文，只考虑字母数字字符和忽略例。 
例如
“A man, a plan, a canal: Panama”一是一个回文。
“race a car”不是回文。
注：
你认为字符串可能是空的吗？这是面试时要问的一个好问题。
对于这一问题的目的，我们定义了空字符串作为有效的回文。 
*/
//分析：从两头往中间扫
class Solution {
public:
    bool isPalindrome(string s) {
        transform(s.begin(),s.end(),s.begin(),::tolower);
        auto left=s.begin(),right=prev(s.end());
        while(left<right){
            if(!::isalnum(*left))
                ++left;
            else if(!::isalnum(*right))
                --right;
            else if(*left!=*right)
                return false;
            else{
                left++;
                right--;
            }
        }
        return true;
    }
};

发表于 2017-07-25 10:30:57 回复(1)

OfferOfferOfferOfferOffer

public class Solution {
    public boolean isPalindrome(String s) {
        String str = s.replaceAll("[^\\w]","");//采用正则表达式，完美解决问题
        if(str.length()==0||str.length()==1){
            return true;
        }
        String ss = str.toLowerCase();
        int n = (ss.length()-1)/2;
        for(int i=0;i<=n;i++){
            if(ss.charAt(i)!=ss.charAt(ss.length()-1-i)){
                return false;
            }
        }
        return true;
    }
}

发表于 2017-07-06 17:55:01 回复(2)

LinuX18

class Solution {
public:
    bool isPalindrome(string s) 
    {
        int left = 0, right = s.length()-1;
        while(left<right)
        {
            if(!isalnum(s[left])) left++;
            else if(!isalnum(s[right])) right--;
            else if(tolower(s[left++]) != tolower(s[right--]))
                return false;
        }
        return true;
    }
};

发表于 2017-07-06 17:45:03 回复(0)

后劲好大

public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() == 0)
        	return true;
        
        int i = 0, j = s.length() - 1;
        while(i < j && i < s.length() && j >= 0){
        	while(i < j && (!Character.isAlphabetic(s.charAt(i)) 
        		&& !Character.isDigit(s.charAt(i))))
        		i++;
        	while(i < j && (!Character.isAlphabetic(s.charAt(j)) 
            		&& !Character.isDigit(s.charAt(j))))
            		j--;
        	if(i < j && Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))
        		return false;
        	i++;
        	j--;
        }
        return true;
    }
}

发表于 2017-06-05 21:55:18 回复(1)

Java

溪苏

public boolean isPalindrome(String s) {

if(s==null||s.trim()==""){

return false;

}

s = s.toLowerCase().trim();

char[] cs = s.toCharArray();

int first = 0;

int last = cs.length-1;

while(first<=last){

if(cs[first]!=cs[last]){

return false;

}

first++;

last--;

}

return true;

}

这个写法有什么问题吗 eclipse上测试没什么问题但是牛客上一个a的时候就显示false

发表于 2017-04-09 11:50:33 回复(3)

Java

詆調壹點

public class Solution {
    public static boolean isPalindrome(String s) {
		int i = 0;
		int j = s.length() - 1;
		while (i < j) {
			while (i < j && ! (Character.isDigit(s.charAt(i)) || Character.isLetter(s.charAt(i))))
				i ++;
			while (i < j && ! (Character.isDigit(s.charAt(j)) || Character.isLetter(s.charAt(j))))
				j --;
			if(i < j && Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) return false;
			i ++;
			j --;
		}
		return true;
	}
}

发表于 2017-03-19 20:27:55 回复(0)

哈姆雷姆

class Solution {

public:

bool isPalindrome(string s) {

if(s.empty())

return true;

int begin = 0,end = s.size()-1;

while(begin<=end){

if(!isalnum(s[begin]))

begin++;

else if(!isalnum(s[end]))

end--;

else{

if(s[begin]!=s[end]&&(s[begin]-s[end])!=('a'-'A')&&(s[begin]-s[end])!=('A'-'a'))

return false;

begin++;

end--;

}

return true;

}

};

发表于 2016-07-14 08:29:34 回复(0)

JacobGo！

package go.jacob.day726;

/**
 * 125. Valid Palindrome
 * 
 * @author Jacob
 *
 */
public class Demo1 {
	/*
	 * 476 / 476 test cases passed. Status: Accepted Runtime: 9 ms
	 */
	public boolean isPalindrome(String s) {
		if (s.isEmpty()) {
			return true;
		}
		//申请两个指针
		int left = 0, right = s.length() - 1;
		char cLeft, cRight;
		while (left < right) {
			cLeft = s.charAt(left);
			cRight = s.charAt(right);
			//Character有现成的isLetterOrDigit()方法，所以不需要自己编写相应函数
			if (!Character.isLetterOrDigit(cLeft))
				left++;
			else if (!Character.isLetterOrDigit(cRight))
				right--;
			else {
				if (Character.toLowerCase(cLeft) != Character.toLowerCase(cRight))
					return false;
				left++;
				right--;
			}
		}
		return true;

	}

}

发表于 2017-07-26 10:08:07 回复(0)