---
# System prepended metadata

title: Leetcode 214
tags: [LeetCode]

---

# 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;
    }


