shortest_palindrome

hitzzc · hitzzc · commit 8694d0ae709f · 2016-10-16T23:39:44.000+08:00
diff --git a/README.md b/README.md
@@ -171,6 +171,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [210. Course Schedule II](https://github.com/hitzzc/go-leetcode/tree/master/course_schedule_II)
 #### [211. Add and Search Word - Data structure design](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
 #### [213. House Robber II](https://github.com/hitzzc/go-leetcode/tree/master/add_and_search_word)
+#### [214. Shortest Palindrome (unsolved)](https://github.com/hitzzc/go-leetcode/tree/master/shortest_palindrome)
 
 
 
diff --git a/shortest_palindrome/shortest_palindrome.go b/shortest_palindrome/shortest_palindrome.go
@@ -0,0 +1,31 @@
+package shortest_palindrome
+
+func shortestPalindrome(s string) string {
+	matrix := make([][]bool, len(s))
+	for i := range matrix {
+		matrix[i] = make([]bool, len(s))
+	}
+	for i := len(matrix) - 1; i >= 0; i-- {
+		for j := i; j < len(matrix[i]); j++ {
+			if j == i || s[i] == s[j] && (i+1 == j || matrix[i+1][j-1]) {
+				matrix[i][j] = true
+			}
+		}
+	}
+
+	p := len(s) - 1
+	for ; p >= 0; p-- {
+		if matrix[0][p] {
+			break
+		}
+	}
+	return reverse(s[p+1:]) + s
+}
+
+func reverse(s string) string {
+	bytes := make([]byte, len(s))
+	for i := range s {
+		bytes[len(s)-i-1] = s[i]
+	}
+	return string(bytes)
+}
