剑指offer

剑指offer018-有效的回文

有效的回文

Posted by 高明 on 2020-01-01

剑指offer018-有效的回文

题目

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

本题中，将空字符串定义为有效的 回文串 。

 

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

 

提示：

  • 1 <= s.length <= 2 * 105
  • 字符串 s 由 ASCII 字符组成

 

注意：本题与主站 125 题相同： https://leetcode-cn.com/problems/valid-palindrome/

Related Topics
  • 双指针
  • 字符串

  • 👍 9
  • 👎 0

    • 思路

    一开始的想法肯定是先去掉非法的字符，全部转化为小写，判断该字符串左右相等

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public boolean isPalindrome(String s) {
            s = s.toLowerCase();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if ((Character.isLetterOrDigit(s.charAt(i)))) {
                    sb.append(s.charAt(i));
                }
            }
            return sb.toString().equals(sb.reverse().toString());
        }
    }

    这里要注意数字和字符的判断

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public boolean isPalindrome(String s) {
            s = s.toLowerCase();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
                if ((Character.isLetterOrDigit(s.charAt(i)))) {
                    sb.append(s.charAt(i));
                }
            }
            return sb.toString().equals(sb.reverse().toString());
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:5 ms,击败了17.77% 的Java用户
    内存消耗:38 MB,击败了96.98% 的Java用户
    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 {
        int offset = 'a' - 'A';
        public boolean isPalindrome(String s) {
            int n = s.length();
            int left = n - 1;
            for (int i = 0; i < s.length(); i++) {
                if (!Character.isLetterOrDigit(s.charAt(i))) {
                    continue;
                }
                while (!Character.isLetterOrDigit(s.charAt(left)) && left > 0) {
                    left--;
                }
                if (convert(s.charAt(i)) != convert(s.charAt(left))) {
                    return false;
                }
                left--;
            }
            return true;
        }

        public char convert(char c) {
            if (c >= 'A' && c <= 'Z') {
                return (char) (c + offset);
            }
            return c;
        }
    }
    1
    2
    3
    解答成功:
    执行耗时:3 ms,击败了60.37% 的Java用户
    内存消耗:38.5 MB,击败了45.08% 的Java用户
    FEATURED TAGS
    剑指offer
    FRIENDS