Блог

Я видел другие рекурсивные вопросы по палиндрому и видел ответы, но тот, который у меня есть, немного отличается. Он должен иметь возможность проверять строку с пробелами и пунктуацией и игнорировать их (я знаю, технически они не являются палиндромами), поэтому такие строки, как «Мадам, я Адам», должны возвращать true, но моя программа этого не делает. Вот что у меня есть:

 public static boolean isPalindrom(String s){
        System.out.println(s);
        if (!Character.isLetter(s.charAt(0))){
            isPalindrom(s.substring(1,s.length()));
        }
         if (!Character.isLetter(s.charAt(s.length()-1))){
            isPalindrom(s.substring(0,s.length()-1));
        }
         if (s.length() == 1){

            return true;
        }
         if (s.length() == 2){
            if (s.substring(0,1).equalsIgnoreCase(s.substring(s.length()-1))){

                return true;
            }
            else
                return false;
        }
        if (!(s.substring(0,1).equalsIgnoreCase(s.substring(s.length()-1)))){

            return false;
        }

            return isPalindrom(s.substring(1,s.length()-1));

    }
  

Проблема в том, что как только он начинает разворачивать рекурсию, строки, содержащие пробелы и знаки препинания, начинают возвращать false. Я не уверен, что делать. Я возился, пробуя разные решения уже около часа.

p.s. Я стараюсь не использовать регулярные выражения для удаления пробелов, знаков препинания и тому подобного.

Вы не возвращаете результат первых двух isPalindrom (проверка которых на наличие случаев начала завершаться неудачей сейчас …):

   if (!Character.isLetter(s.charAt(0))){
        return isPalindrom(s.substring(1,s.length()));
    }
     if (!Character.isLetter(s.charAt(s.length()-1))){
        return isPalindrom(s.substring(0,s.length()-1));
    }
  

Когда вы доберетесь до одного, вам просто нужно двигаться вперед с ним. вот так. Я оставляю на ваше усмотрение заполнение пробелов (особые случаи, lastNonIgnoredChar и т.д.)

 char[] ignored = new char[] { ',' , ' ', '.'};

int firstNonIgnoredChar(String s) {
    for(int i = 0; i < s.length(); i  ) {
        boolean found = false;
        for(char c : ignored) {
            if( c == s.charAt(i) ) found = true;
        }
        if(!found) return i;
    }
    return -1; // no good characters
}

boolean isPal(String s) {
    int first = firstNonIgnoredChar(s);
    int last = lastNonIngoredChar(s);

    if(s.length() == 0) return true;
    if(s.length() == 1) return true;

    return first < last
        amp;amp; s.charAt(first) == s.charAt(last)
        amp;amp; isPal(s.substring(first   1, last - 1);
}
  

Нерекурсивный метод, который выполняется под или при O (n / 2) в наихудшем случае (полный поиск). Это более эффективно, когда строка длинная… Вот реализация…

 class PalindromeClass {

    /**
     * This method will run under or at O(n/2) with n = sentence.size()
     * @param sentence is a given String sentence.
     * @return true if the given sentence is a palindrome.
     */
    public static boolean isPalindrome(String sentence) {
        sentence = sentence.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
        char[] sentenceChars = sentence.toCharArray();
        for (int i = 0; i < sentenceChars.length / 2; i  ) {
            if (sentenceChars[i] != sentenceChars[sentenceChars.length - 1 - i]) {
                return false;
            }
        }
        return true;
    }
  

Выполнение этого с короткими, длинными и неправильными параметрами дает вам правильные значения…

 public static void main(String[] args) {

String wrong = "ABCA";
System.out.println("Is '"   wrong   "' a palindrome? ");
System.out.println(isPalindrome(wrong));

String none = "A'";
System.out.println("Is '"   none   "' a palindrome? ");
System.out.print(isPalindrome(none));

String a = "Madam, I'm Adam";
System.out.println("Is '"   a   "' a palindrome? ");
System.out.println(isPalindrome(a));

String b = "abba";
System.out.println("Is '"   b   "' a palindrome? ");
System.out.println(isPalindrome(b));

String toyota = "A Toyota. Race fast, safe car. A Toyota.";
System.out.println("Is '"   toyota   "' a palindrome? ");
System.out.println(isPalindrome(toyota));

String longestPalindrome = "Do good? I? No! Evil anon I deliver. I maim "  
    "nine more hero-men in Saginaw, sanitary sword a-tuck, Carol, I -- lo! "  
    "-- rack, cut a drowsy rat in Aswan. I gas nine more hero-men in Miami. "  
    "Reviled, I (Nona) live on. I do, O God!";
System.out.println("Is '"   longestPalindrome   "' a palindrome? ");
System.out.println(isPalindrome(longestPalindrome));
}
  

}

Вот результат выполнения…

 Is 'ABCA' a palindrome? false
Is 'a' a palindrome? true
Is 'Madam, I'm Adam a palindrome?' true
Is 'abba a palindrome? true'
Is 'A Toyota. Race fast, safe car. A Toyota.' a palindrome? true
Is 'Do good? I? No! Evil anon I deliver. I maim nine more hero-men in Saginaw, sanitary sword a-tuck, Carol, I -- lo! -- rack, cut a drowsy rat in Aswan. I gas nine more hero-men in Miami. Reviled, I (Nona) live on. I do, O God!' a palindrome? true