验证回文字符串

男娘i 2021-06-10 20:38 442阅读 0赞

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70][] 思路： ###

首先过滤转成char数组，然后进行比较，注意，这个方法有较大弊端。

class Solution {
        public boolean isPalindrome(String s) {
            if(s==null||s.length()==1)
                return true;
            s = s.toLowerCase();
            //过滤成char数组,x记录数组长度
            int x=0;
            char[] arr = new char[s.length()];
            for(int i=0;i<s.length();i++) {
                char c = s.charAt(i);
                if(Character.isLetterOrDigit(c)) {
                    arr[x] = c;
                    x++;  
                }
            }
            //此时x为charArr的长度
            int cmpTimes = x >> 1;
            for(int i =0;i<cmpTimes;i++) {
                if(arr[i] != arr[x-1-i]) {
                    return false;
                }
            }
            return true;
        }
    }

这种方法char数组的长度是不固定的，而我申请了s.length的长度，会造成浪费。时间复杂度O(n),空间复杂度O(n).

class Solution {
        public boolean isPalindrome(String s) {
            s = s.toLowerCase();
            StringBuilder str = new StringBuilder(s.length());
            for(char c: s.toCharArray())
            {
                if((c>='0'&&c<='9')||(c>='a'&&c<='z'))
                {
                    str.append(c);
                }
             }
           return str.toString().equals(str.reverse().toString());
        }
    }

可以采用StringBuilder的reverse方法,也是char\[\]的原理。时间复杂度O(n),空间复杂度O(n).

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

这个算法很纯粹，就是依次比较。时间复杂度O(n^2),空间复杂度O(1).

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70]: /images/20210518/14242434aabc47c6aa84527e68966f70.png