我想到了一种解法,但是它的时间复杂度为O(n^2)。
算法1: 步骤: 这是一种暴力方法 1. 有两个for循环 对于i = 1到i小于array.length-1 对于j=i+1到j小于array.length 2. 这样就可以从数组中获得每个可能组合的子串。 3. 拥有一个回文函数来检查一个字符串是否是回文的。 4. 因此,对于每个子串(i,j),调用此函数,如果它是回文的,则将其存储在一个字符串变量中。 5. 如果你发现下一个回文子串大于当前子串,则用当前子串替换它。 6. 最后,您的字符串变量将具有答案。
问题: 1. 这个算法的时间复杂度为O(n^2)。
算法二: 1. 反转字符串并将其存储在不同的数组中 2. 现在在两个数组之间找到最大匹配的子字符串 3. 但这也需要O(n^2)的时间
你们能想出一个更好的算法吗?如果可能的话,请使用O(n)时间。
O(n^2)
的时间来获取所有子字符串,再需要O(n)
的时间检查它们是否是回文,总共需要O(n^3)
的时间复杂度? - Skylar Saveland