Leetcode isPalindrome失败

Question

我想知道如何让我的isPalindrome更快地传递leetcode中更大的字符串？这是input我的代码因超出时间限制而失败。

import java.util.Stack;
public class Palindrome {
    public boolean isPalindrome(String s){
        Stack<Character> charStack = new Stack<Character>();
        String alphanumericStr="";
        for (int i=0; i<s.length(); i++){
            if (Character.isLetterOrDigit(s.charAt(i))){
                alphanumericStr=alphanumericStr+String.valueOf(s.charAt(i)).toLowerCase();
            }
        }
        System.out.println("str = [" + alphanumericStr + "]");
        if (alphanumericStr.length()==0 || alphanumericStr.length()==1){
            return true;
        }

        if (alphanumericStr.length()%2 == 0){
            if (s.charAt(s.length()/2) != s.charAt((s.length()/2) -1)){
                return false;
            }
        }
        System.out.println( (alphanumericStr.length()/2)-1 );
        for (int i=0; i< (alphanumericStr.length()/2);i++){

                charStack.push(alphanumericStr.charAt(i));

        }

        for (int i=(alphanumericStr.length()/2)+1; i<alphanumericStr.length(); i++){
            if (!charStack.empty()) {
                if (Character.isLetterOrDigit(alphanumericStr.charAt(i))) {
                    if (charStack.pop() != alphanumericStr.charAt(i)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    public static void main (String[] argc){
        String mimim = "a.";
        Palindrome palindrome=new Palindrome();
        boolean res= palindrome.isPalindrome(mimim);
        System.out.println("result is  = [" + res + "]");
        return;
    }

}

Answer 1

这应该不是一个大问题。使用堆栈可能会遇到大字符串的内存问题，但我会说你根本不需要堆栈。

只需获取字符数组并使用两个索引来检查字符。从字符串的前面和后面开始，推进每个索引，直到你点击一个字母数字字符，检查两者是否相等，忽略大小写前进（当然你从前面开始向后“推进”一个索引）。

如果字符不相等（字符串不是回文）或向后索引小于或等于前向索引，则停止。

编辑：

另一个可能不是那么快但更短的方法（在代码方面）将是：

//remove all non-alphanumeric chars
String forwardStr = yourString.replaceAll("[^a-zA-Z0-9]","");

//get a reversed version of the strinf
String revStr = new StringBuilder(forwardStr).reverse().toString();

//check equality ignoring case
boolean isPalindrome = forwardStr.equalsIgnoreCase( revStr );

Answer 2

关于leetcode的我的C＃解决方案

    var length = s.Length;

    if (length == 0) return false;

    var dic = new Dictionary<char, int>();

    for (var i = 0; i < length; i++)
    {
        if (dic.ContainsKey(s[i]))
        {
            dic[s[i]]++;
            continue;
        }

        dic.Add(s[i], 1);
    }

    var odd = 0;
    foreach (var pv in dic)
    {
        if (odd > 1) return false;
        if (pv.Value % 2 != 0) odd++;
    }

    //code reach here means string IsPpalindorme  
    //but when continue use dictionary build all palindrome permutation, i also had time limit exceeded with string like "aabbhijkkjih" my recursive method seems not right. 

Answer 3

代码的时间复杂度为O（N）。您可以尝试使用两个指针同时扫描输入字符串从两侧到中间。所以时间复杂度将下降到O（logN）。这是我的示例JAVA代码。

public class Palindrome {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }

        int front = 0;
        int end = s.length() - 1;
        while (front < end) {
            while (front < s.length() && !isvalid(s.charAt(front))){//check border
                front++;
            }

            if (front == s.length()) { // for emtpy string   
                return true; 
            }           

            while (end >= 0 && ! isvalid(s.charAt(end))) {//check border
                end--;
            }

            if (Character.toLowerCase(s.charAt(front)) != Character.toLowerCase(s.charAt(end))) {
                break;
            } else {
                front++;
                end--;
            }
        }

        return end <= front; 
    }

    //check if the character is a letter or a digit
    private boolean isvalid (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }
}

Answer 4

你的算法的Big-O只是O（n），它只是你用了太多的循环，所以它浪费你的时间很多。

如果你只想找到更好的leetcode问题解决方案，只需去讨论页面，他们确实有很多好的答案。

如果您仍未获得他们的想法，可以在StackOverFlow上查看

Answer 5

public boolean isPalindrome(String s) {
    char [] chars = s.toLowerCase().replaceAll("[^a-z0-9]", "").toCharArray();
    for (int i=0; i< chars.length; i++) {
        if (!Character.isLetterOrDigit(chars[i])){
            continue;
        }
        if (chars[i] != chars[chars.length-1 -i]) {
            return false;
        }
    }

    return true;

}