# Leetcode 214
###### tags: `LeetCode`
**My bad solution**
Runtime: 324 ms, faster than 5.32%
Memory Usage: 36.3 MB, less than 100.00%

class Solution {
public String shortestPalindrome(String s) {
if(s.equals(""))return "";
int len = s.length() -1;
int recode = ru(0 , len , s );
StringBuffer sb = new StringBuffer();
if(recode == len) {
return s ;
}else {
sb.append(s.substring(recode+1, len+1));
sb.reverse();
}
return sb.toString() + s ;
}

private static int ru(int startIDX ,int len , String s ) {
int recode = 0;

for (int i = startIDX , j = len ; j > 0;) {
if (s.charAt(i) == s.charAt(j)) {
recode = i == startIDX ? j : recode;
i++;
j--;
} else {
j = len--;
recode = 1;
i = startIDX;

}
if(i == j || i == j+1) {
if(recode==1 && s.charAt(0) != s.charAt(1)) {
recode = 0;
}
break;
}
}
return recode;
}
}

**Refer from LeetCode solution**
Runtime: 1 ms, faster than 100.00%
Memory Usage: 35.7 MB, less than 67.04%

public String shortestPalindrome(String str) {
int j = 0;
int n = str.length();
char[] c = str.toCharArray();
for (int i = n - 1; i >= 0; --i) {
if (c[i] == c[j]) {
++j;
}
}
if (j == n) {
return str;
}
String suffix = str.substring(j);
String prefix = new StringBuilder(suffix).reverse().toString();
String mid = shortestPalindrome(str.substring(0, j));
return prefix + mid + suffix;
}