【LeetCode#125】三种解法

红太狼 2023-02-19 08:29 3阅读 0赞

## LeetCode\#125 ##

*  [LeetCode项目地址：持续更新ing… (欢迎催更)][LeetCode_ing_]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTA2NjQ3_size_16_color_FFFFFF_t_70]

## 思路 ##

回文串最常见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());
    }

[LeetCode_ing_]: https://github.com/HelloSummer5/LeetCodeDemo
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTA2NjQ3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200619180458773.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyMTA2NjQ3,size_16,color_FFFFFF,t_70