最長迴文子串澄清

Question

方法3（動態規劃）[接受]

爲了提高在蠻力解決方案，我們首先觀察我們如何能夠 避免不必要的重新計算，而驗證迴文。 考慮「ababa」這個案例。如果我們已經知道 'bab''是一個迴文，很顯然''ababa''必須是迴文，因爲這兩個字母是相同的左右兩端 。

這將產生直接的DP解決方案，這是我們首先初始化 了一個和兩個字母迴文，並一步奮鬥找到所有 三個字母迴文，等等...

複雜性分析

時間複雜度：O（n^2）這給我們提供了一個運行時間爲O（n^2）的複雜度爲 。

空間複雜度：O（n^2）。它使用O（n^2）空間 來存儲表格。

我在網上閱讀了上述解決方案以解決這個問題，並且對它有一些疑問（如果這不是正確的論壇發佈請讓我知道）。這是我對如何解決這個問題的理解：保存所有的一字節迴文。然後對於其中的每一個，如果左邊的char等於右邊的char，則保留它。如果不符合該條件，請停止處理此子字符串。繼續直到結束。

這是正確的嗎？如果是這樣，這是如何轉化爲O（N^2）算法？是否是因爲在最壞的情況下，我們必須通過字符串N遍來逐一遞增每個可能的迴文。這部分對我來說並不直觀。

Answer 1

您的解釋是正確的。
在最壞的情況下，我們需要檢查所有長度增加的子字符串。我們首先檢查長度爲1的所有子字符串，然後檢查長度爲3的所有子字符串，依此類推。此外，我們還需要考慮"abba"類型的迴文，因此我們還需要檢查所有長度均勻的候選人。所以在最壞的情況下，我們需要驗證給定輸入字符串的每個可能的子字符串。

長度n的給定的字符串的子串的總數爲n(n + 1)/2

n * (n + 1)/2 = n^2/2 + n/2 = O(n^2) 

否則爲迴文單一驗證步驟可以在O(1)來完成，因此，總運行時間爲O(n^2)。