博客

LeetCode#125

• 
  LeetCode项目地址：持续更新ing… (欢迎催更)
  
  
  

思路

回文串最常见3种解法：双指针、栈、字符串反转

双指针

• PS：面试中不建议用正则，因为考察不出你的水平，面试官肯定还会问别的方法实现过滤

    public static boolean isPalindrome2(String s) {

// 过滤非字母数字字符, \\W ==>  [^a-zA-Z0-9]，面试时用正则可能还会问另一种方法
        String str = s.replaceAll("\\W", "");
        // 双指针
        int start = 0, end = str.length() - 1;
        while (start < end) {
            if (Character.toUpperCase(str.charAt(start)) != Character.toUpperCase(str.charAt(end))) return false;
            start++;
            end--;
        }
        return true;
}

栈

• 将字符串前一半放入栈中，遍历后半段并且跟栈顶元素比较，相同则pop弹出，否则直接返回false

public static boolean isPalindrome2(String s) {
	Stack stack = new Stack();
    // 去除非字母非数字
    StringBuffer stringBuffer = new StringBuffer();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isLetterOrDigit(c)) {
            stringBuffer.append(Character.toLowerCase(c));
        }
    }
    // 将前一半字符串入栈
    int l = stringBuffer.length();
    for (int i = 0; i < l / 2; i++) {
        stack.push(stringBuffer.charAt(i));
    }
    // 栈里元素与后部分字符串比较
    int start = l % 2 == 1 ? l / 2 + 1 : l / 2; // 取中间数往后开始遍历
    for (int i = start; i < l; i++) {
        if ((char)stack.peek() == stringBuffer.charAt(i)){
            stack.pop();
        }else return false;
    }

    return true;
}
}

字符串反转

• 不是很建议刷算法题直接调用现成的方法，可自己实现一下

public static boolean isPalindrome2(String s) {
StringBuffer stringBuffer = new StringBuffer();
        // 去除非字母非数字
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                stringBuffer.append(Character.toLowerCase(c));
            }
        }
        // 反转比较字符串
        StringBuffer stringBufferRev = new StringBuffer(stringBuffer).reverse();
        return stringBuffer.toString().equals(stringBufferRev.toString());
}