4

文字列が回文かどうかをチェックするクラスがあります。2 つの質問があります。

1) これは回文をチェックする最も効率的な方法ですか? 2) これは再帰的に実装できますか?

public class Words {

    public static boolean isPalindrome(String word) {
    String pal = null;
    word = word.replace(" ", "");
    pal = new StringBuffer(word).reverse().toString();
    if (word.compareTo(pal) == 0) {
        return true;
    } else {
        return false;
    }

    }

}

これをテストするためのテストクラスを用意してください...その必要性を疑いますが、上記の2つの質問のいずれかで私を助けることができるように誰かがそれを試してみたいと思っているなら、ここにあります...

public class testWords {

    public static void main(String[] args) {
    if (Words.isPalindrome("a") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("cat") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("w o    w") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("   a  ") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("mom!") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }

    }

}

事前にヘルプや入力に感謝します:)

4

6 に答える 6

6

これは別の再帰的な解決策ですが、配列を使用すると、再帰呼び出しで文字列よりもパフォーマンスが向上する可能性があります（substringorを回避しますcharAt）。

private static boolean isPalindrome(final char[] chars, final int from,
        final int to) {
    if (from > to) return true;
    return chars[from] != chars[to] ? false 
                                    : isPalindrome(chars, from + 1, to - 1);
}

public static boolean isPalindrome(final String s) {
    return isPalindrome(s.toCharArray(), 0, s.length() - 1);
}

アイデアは、配列内の 2 つの位置を追跡し、1 つは先頭に、もう 1 つは最後に、位置を中心に向かって移動し続けるというものです。

位置が重なり合って通過すると、すべての文字の比較が完了し、それまでのすべての文字が一致しました。文字列は回文です。

各パスで文字を比較し、一致しない場合、文字列は回文ではありません。そうでない場合は、位置を近づけます。

于 2013-03-30T20:05:02.617 に答える
5

回文であることを確認するには、実際には真ん中の文字までチェックするだけで十分です。つまり、次のように簡略化できます。

// Length of my string.
int length = myString.length();

// Loop over first half of string and match with opposite character.
for (int i = 0; i <= length / 2; i++) {
    // If we find one that doesn't match then return false.
    if (myString.charAt(i) != myString.charAt(length - 1 - i)) return false;
}

// They all match, so we have found a palindrome!
return true;

再帰的な解決策は非常に可能ですが、パフォーマンス上の利点はありません (おそらく読みにくいです)。

于 2013-03-30T19:42:25.150 に答える
1

私の2セント。人々がさまざまな方法で問題を解決するのを見るのはいつでもうれしいものです。もちろん、これは最も効率的なアルゴリズム メモリや速度ではありません。

public static boolean isPalindrome(String s) {

    if (s.length() <= 1) { // got to the middle, no need for more checks
        return true;
    }

    char l = s.charAt(0); // first char
    char r = s.charAt(s.length() - 1); // last char

    if (l == r) { // same char? keep checking
        String sub = s.substring(1, s.length() - 1);
        return isPalindrome(sub);
    }

    return false;
}
于 2014-03-21T06:00:25.423 に答える