如何將給定的字符串轉換爲迴文？

Question

我有一個面試問題是：

「轉換一個給定的字符串的迴文，提供的輸出 （迴文字符串）應包含給定字符串的子串」

所以我這樣做，給root作爲輸入，我會找到該字符串的反轉，並將其附加到給定的輸入。所以我得到的字符串：

roottoor 

這是一個迴文，還含有I/P（root）出現在O/P。

鑑於解決方案，該interverwer說，它不是最優的解決方案，你可以給一個最佳的解決方案嗎？

我無法找到任何與此不同的地方。

其他解決方案？

他說它需要用Java來完成。

Answer 1

對於給定的字符串s，請在s的末尾找到最長的子字段s1，該字段已經是迴文。然後把s\s1的反面放在最後。

例如，對於輸入字符串"lambada"，"ada"是迴文，所以你只需要添加的"lamb"相反，結果是"lambadabmal"。

編輯：考慮maartinus的回答，您也應該檢查相反的方向，並選擇導致更短的迴文的一個：

對於一個給定的字符串s，找到最長子s1之初s這已經是迴文。然後在開始處插入s\s1的反向。

例如，對於輸入字符串"arafat"，"ara"是迴文，所以你只需要插入的"fat"相反的開頭和結果是"tafarafat"。

Answer 2

另一個答案明顯錯過了看開始。示例

racecars -> racecarsracecar // when only the end is considered 

racecars -> sracecars  // when the start is considered 

只看兩端並返回更好的結果。