当前位置：首页 > news >正文

面试经典150题——验证回文串

news 2025/8/8 9:09:48

面试经典150题 day25

- - 题目来源
  - 我的题解
  - - 方法一双指针
    - 方法二双指针空间优化

题目来源

力扣每日一题；题序：125

我的题解

方法一双指针

首先去除掉字符串中的无用字符，并将英文字符转换为小写，然后使用双指针来判断是否是回文串。

时间复杂度：O(n)
空间复杂度：O(n)

public boolean isPalindrome(String s) {s=trimAndToLower(s);int n=s.length();int left=0,right=n-1;while(left<right){if(s.charAt(left++)!=s.charAt(right--)){return false;}}return true;
}
public String trimAndToLower(String s){StringBuilder sb=new StringBuilder();int n=s.length();for(int i=0;i<n;i++){char ch=s.charAt(i);if((ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')){sb.append(ch);}else if(ch>='A'&&ch<='Z'){sb.append((char)(ch-'A'+'a'));}}return sb.toString();
}

方法二双指针空间优化

不再去删除无效字符，并将英文字符转为小写。而是在遍历过程中直接判断。

时间复杂度：O(n)
空间复杂度：O(1)

public boolean isPalindrome(String s) {int n=s.length();int left=0,right=n-1;while(left<right){while(left<right&&!isUsedChar(s.charAt(left))){left++;}while(left<right&&!isUsedChar(s.charAt(right))){right--;}if(toLower(s.charAt(left++))!=toLower(s.charAt(right--))){return false;}}return true;
}
public boolean isUsedChar(char ch){return (ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')||(ch>='A'&&ch<='Z');
}
public char toLower(char ch){if((ch>='a'&&ch<='z')||(ch>='0'&&ch<='9')){return ch;}else{return (char)(ch-'A'+'a');}
}