题目

【暴力法】解题思路

// abcd
// 反转 dcba
// 合并 dcba abcd
// 要删除公共部分a
//
// 推广：
// 字符串aA，a是回文前缀，则题解是A'aA，其中A'是A的反转；
//
// 方法1： 暴力法
// 1）遍历求aA的最长回文前缀a，进而获得剩余部分A；
// 2）答案是A'aA
//

【暴力法】代码

package main

// 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
// 输入: "abcd"
// 输出: "dcbabcd"
//
//      abcd
// 反转 dcba
// 合并 dcba abcd
// 要删除公共部分a
//
// 推广：
// 字符串aA，a是回文前缀，则题解是A'aA，其中A'是A的反转；
//
// 方法1： 暴力法
// 1）遍历求aA的最长回文前缀a，进而获得剩余部分A；
// 2）答案是A'aA
//

// 判断是否为回文字符串
func isPalindromeStr(str string) bool {
    for i,j := 0, len(str)-1; i<j; i, j = i+1, j-1 {
        if str[i] != str[j] {
            return false
        }
    }

    return true
}

// 反转字符串
func reverseStr(str string) string {
    runeStr := []rune(str)
    for from, to := 0, len(runeStr)-1; from < to; from, to = from + 1, to -1 {
        runeStr[from], runeStr[to] = runeStr[to], runeStr[from]
    }

    return string(runeStr)
}

func shortestPalindrome(str string) string {
    var ans string
    
    for i:=len(str); i>=0; i-- {
        prefix := str[:i]
        if isPalindromeStr(prefix) {
            ans = reverseStr(str[i:]) + str
            break
        }
    }

    return ans
}

【暴力法】执行结果