獲取迴文的反向子串

-3

給定一個由英文字母組成的小寫字符組成的字符串，我們希望從字符串中反轉一個子串，以使字符串變成迴文。獲取迴文的反向子串

注意：一個迴文是一個等於它的反向的字符串。

我們需要判斷是否存在一些可反轉的字符串以將字符串轉換爲迴文。

例如：設字符串爲「zakdakdz」。然後，該字符串的答案是肯定的，因爲我們可以反向指標4和6之間的串獲得zakddkaz

的基本方法：設法扭轉每串並檢查是否我們得到迴文與否。然而，這是一個很長的字符串的壞方法。

那麼有沒有更好的方法來解決它？

能否比O（N^2）方法更快？

來源

2014-10-10 cook topcoder

是的，當然有。他們可能會考慮從頭到尾遍歷字符串，並比較字符。 – 2014-10-10 02:27:41

@JerryCoffin它是什麼？ – 2014-10-10 02:28:15

@JerryCoffin你的意思是「他們在想什麼」？ – 2014-10-10 02:30:40

這裏是一個二次算法，從立方下來（我強烈懷疑進一步的改進，線性時間或可能n log n是可能的）。假設字符串如下所示：

X...X .

我聲稱，如果存在一個子，其反轉使這串迴文，則存在這樣的子串不包括任何X。如果它包含X s，則該字符串已經是迴文。如果僅包括一個X，說由對稱的第一個，那麼子要像

X...X...X , 
^^^^^

因爲第二X就是不爲所動。我們可以將反向子串縮小到

X...X...X . 
^^^

二次時間算法是從末端掃描直到發現不匹配。然後嘗試從左側不匹配的字母開始的所有子字符串和以右側不匹配的字母結尾的所有子字符串。

來源

2014-10-10 03:00:15

你可以提供一些僞代碼嗎？它會讓事情更清楚 – 2014-10-10 08:12:24

長度小於2的字符串是迴文，並保持每個子字符串顛倒。如果我不那麼懶惰，我可能會
從兩端向內掃描較長的字符串以獲得字符差異（或在中間會議），然後從中間向外掃描。知道非迴文區域，如果它們是相同的，則將其翻轉成整個字符串爲迴文。

來源

2014-10-10 09:27:36 greybeard

你能提供一些僞代碼嗎？還記得我們只能反轉一個字符串 – 2014-10-10 11:21:02

@cook topcoder：我正要嚴厲地回覆。「記住」和「我們」更多的是「分配鈴聲」：描述應用程序，如果既不是作業也不是競爭，或者事先聲明它是什麼，請幫助解決方案。「zakdakdz」：從外面看，'a'（左起第一個）和'd'（左起第一個）（右起第一個）在內部不同，'d'（3）和'a' （4）。如果1-3和4-6（包含）的子串不同，沒有任何一次逆轉會產生迴文，因爲它們相等，選擇一個逆轉。 – greybeard 2014-10-10 19:02:58

我想你沒有得到任何問題 – 2014-10-10 20:53:18

獲取迴文的反向子串

回答

相關問題