驗證回文串
題目地址：https://leetcode-cn.com/problems/valid-palindrome/
給定一個字串，驗證它是否是回文串，只考慮字母和數字字符，可以忽略字母的大小寫，
說明：本題中，我們將空字串定義為有效的回文串，
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
示例 2:
輸入: "race a car"
輸出: false
解法一：雙指標
首先判斷兩個字串是否是回文串，就是原串與倒序是否相等，那不就是前面寫的反轉字串么，只不過就是首尾交換，換成首尾是否相等，但在此之前我們先要從原串中獲取數字字母串并忽略大小寫
public boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
char[] arr = s.toCharArray();
int n = arr.length;
StringBuilder cs = new StringBuilder();
for (int i = 0; i < n; i++) {
char c = arr[i];
if (check(c)) {
cs.append(change(c));
}
}
n = cs.length();
for(int i = 0; i < n/2; i++){
if(cs.charAt(i) != cs.charAt(n-i-1)){
return false;
}
}
return true;
}
//是否是字母或數字
public boolean check(char c){
return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
//大寫統一轉小寫
public char change(char c){
return c>=65&&c<=90 ? c+=32 : c;
}
解法二：細節優化(雙指標)
我們剛剛是用了兩個回圈，第一個回圈篩選了屬于字母數字的，第二次回圈再判斷字母數字的串有木有重復，其實是冗余的，我們直接在第一個回圈完成即可，最終的目的是看字母數字是否回文但沒必要取出來再做，那樣減少了一個容器和一次遍歷，
public boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
char[] arr = s.toCharArray();
int n = arr.length;
int start = 0;
int end = n - 1;
while(start < end){
while(start < end && !check(arr[start])){
start++;
}
while(start < end && !check(arr[end])){
end--;
}
if(change(arr[start])!=change(arr[end])){
return false;
}
start++;
end--;
}
return true;
}
//是否是字母或數字
public boolean check(char c){
return c>=48&&c<=57 || c>=65&&c<=90 || c>=97&&c<=122;
}
//大寫統一轉小寫
public char change(char c){
return c>=65&&c<=90 ? c+=32 : c;
}
解法三：堆疊
雖然這題雙指標就是比較優的解法，但是前段時間學習了堆疊，因此在這題上用上溫習一下不過空間和效率應該是最低的，我們都知道堆疊是后進先出（LIFO）一種資料結構，這里我們可以用陣列實作一下堆疊完成一下基本的四個方法
class Stack<E>{
List<E> arr = new ArrayList();
int top = -1;
void push(E c){
arr.add(++top,c);
}
E pop(){
E c = peek();
arr.remove(top--);
return c;
}
E peek(){
return arr.get(top);
}
boolean isEmpty(){
return top < 0;
}
}
public boolean isPalindrome(String s) {
if(s == null || s.length() == 0) return true;
char[] arr = s.toCharArray();
int n = arr.length;
Stack<Character> stack = new Stack<>();
List<Character> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
char c = arr[i];
if (check(c)){
stack.push(change(c));
list.add(change(c));
}
}
int index = 0;
while (!stack.isEmpty()){
if (stack.pop() != list.get(index++))
return false;
}
return true;
}
總結
回文串處理的大體方式還是雙指標、反轉或者堆疊，對于此題Character類中提供了判斷是否為數字或字母的方法和轉大小寫的方法，我上面是單獨寫的check(char c)與change(char c)方法，
isLetterOrDigit(char c)
toLowerCase(char c)
利用Java類別庫的話直接有反轉方法當然它里面也是一次遍歷處理，反轉再比較，當然效率是比較低的可以參考
//cs為取出來的只含字母數字的字串
String fz = cs.reverse().toString();
return cs.equals(fz);
總體來說呢可以實作的方式有很多，關注實作本身效率來說雙指標是較優的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232949.html
標籤：其他