例如字符串“ abaccddccefe”中的“ ccddcc”我想到了一個解決方案，但它的運行時間為O（n ^ 2）算法1：步驟：這是一種蠻力方法對于i = 1至i小于array.length的2個for循環，對于j = i + 1至j小于 array.length的-1這樣，您可以從數組中獲取所有可能組合的子字符串具有回文功能，可檢查字符串是否為回文因此，對于每個子字符串（i，j）都調用此函數（如果它是回文）將其存儲在字符串變量中如果找到下一個回文子字符串，并且該子字符串大于當前子字符串，則將其替換為當前子字符串。最后，您的字符串變量將得到答案問題：1.該算法運行時間為O（n ^ 2）。算法2：反轉字符串并將其存儲在不同的數組中現在找到兩個數組之間最大的匹配子字符串但這也需要O（n ^ 2）時間你們能想到一種運行時間更好的算法嗎？如果可能的話O（n）時間
3 回答
拉風的咖菲貓
TA貢獻1995條經驗 獲得超2個贊
您可以使用最長的回文Manacher算法的O(n)時間！它的實現可以在這里和這里找到。
對于輸入，String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它將找到正確的輸出1234567887654321。
尚方寶劍之說
TA貢獻1788條經驗 獲得超4個贊
據我了解的問題，我們可以在中心索引附近找到回文，并在中心的左右兩側進行搜索。鑒于此，并且知道輸入的角落沒有回文，我們可以將邊界設置為1和length-1。注意字符串的最小和最大邊界時，我們驗證對稱索引位置（右和左）上的字符對于每個中心位置是否都相同，直到達到最大上限中心。
外循環為O（n）（最多n-2次迭代），內循環為O（n）（最大（n / 2）-1次迭代）
這是我使用其他用戶提供的示例的Java實現。
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
其輸出如下：
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
添加回答
舉報
0/150
提交
取消