描述
給定一個(gè)字符串琅催，判斷其是否為一個(gè)回文串狞甚。只考慮字母和數(shù)字谜叹，忽略大小寫瞧筛。
你是否考慮過硝枉，字符串有可能是空字符串？這是面試過程中缠黍，面試官常常會問的問題弄兜。
在這個(gè)題目中，我們將空字符串判定為有效回文瓷式。
樣例
樣例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
解釋: "amanaplanacanalpanama"
樣例 2:
輸入: "race a car"
輸出: false
解釋: "raceacar"
挑戰(zhàn)
O(n) 時(shí)間復(fù)雜度挨队，且不占用額外空間。
相關(guān)題目
- 200. 最長回文子串
- 893. 最長回文子串 II
- 891. 有效回文 II
- 745. 回文的范圍
- 744. 前K個(gè)偶數(shù)長度的回文數(shù)和
- 491. 回文數(shù)
- 627. 最長回文串
- 223. 回文鏈表
題目解析
判斷給定字符串是否是回文串蒿往，只需要比較ASCII碼的字母和數(shù)字即可，其它符號跳過
首先介紹兩個(gè)函數(shù)湿弦，在這里使用比較方便
int isalnum(int c);如果c是數(shù)字或大小寫字母瓤漏，返回true
int toupper(int c);將字符c轉(zhuǎn)為大寫
回文串左右是對稱的，所以只需要從兩邊向中間推進(jìn)判斷
參考代碼
public class Solution {
public boolean isPalindrome(String s) {
if (s == null || s.length() == 0) {
return true;
}
int front = 0;
int end = s.length() - 1;
while (front < end) {
while (front < s.length() && !isvalid(s.charAt(front))) { // nead to check range of a/b
front++;
}
if (front == s.length()) { // for empty string “.,,,”
return true;
}
while (end >= 0 && ! isvalid(s.charAt(end))) { // same here, need to check border of a,b
end--;
}
if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
break;
} else {
front++;
end--;
}
}
return end <= front;
}
private boolean isvalid (char c) {
return Character.isLetter(c) || Character.isDigit(c);
}
}
在線評測地址：有效回文串
