私のソリューションが一部の文字列に対してのみ機能する理由に固執しています。たとえば、「sdfbananabasdf」は「bananab」を返しますが、「dtattarrattatddetartrateedre」は無限ループで実行されます。前もって感謝します！
public String longestPalindrome(String s) {
if(isPalindrome(s)) {
return s;
}
String divisionOne = longestPalindrome(s.substring(0,s.length()-1));
String divisionTwo = longestPalindrome(s.substring(1,s.length()));
return (divisionOne.length() >= divisionTwo.length()) ? divisionOne : divisionTwo;
}
private boolean isPalindrome(String s) {
if(s.length() == 1) {
return true;
}
int count = s.length() / 2;
if(s.length() % 2 == 1) {
count++;
}
for(int i = 0; i < count; i++) {
if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {
return false;
}
}
return true;
}
基本的に、あなたのアルゴの時間計算量は O(2^n)
とするf(n)と、長さのある文字列の回文を計算する関数です。n最悪の場合、次のことがわかります。
f(n) = 2*f(n - 1)
f(n - 1) = 2*f(n - 2)
...
f(1) = 1
->f(n)時間計算量はO(2^n)
したがって、長い文字列の場合、プログラムの実行には長い時間がかかります。例のように、29文字の文字列には、O（2 ^ 29）またはO（5 * 10 ^ 8）演算が必要です。
注：実際には、各操作は、2つの追加が必要substringとisPalindrome時間複雑度はO（N * 2 ^ N）だけでなく、O（2 ^ n）が作る操作を、
時間の複雑さを軽減する方法は？動的計画法が答えになるはずです
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加