leetcode-go/oj/tencent-2017-summer/build-palindrome.go

package main

import "fmt"

func main() {
	var s string
	_, err := fmt.Scanln(&s)
	for err == nil {
		res := solve(s)
		fmt.Println(res)
		_, err = fmt.Scanln(&s)
	}
}

func solve(s string) int {
	str, rev := []byte(s), []byte(s)
	n := len(s)
	for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
		rev[l], rev[r] = rev[r], rev[l]
	}
	// dp[i][j] means the LCS of str[:i+1] and rev[:j+1]
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			if str[i-1] == rev[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return n - dp[n][n]
}

func maxInt(x, y int) int {
	if x < y {
		return y
	}
	return x
}