public String shortestPalindrome(String s) {
		if (s.length() <= 1)
			return s;
		int center = (s.length() - 1) / 2;
		String res = "";
		for (int i = center; i >= 0; i--) {
			if (s.charAt(i) == s.charAt(i + 1)) {
				if ((res = check1(s, i, i + 1)) != null)
					return res;
			}
			if ((res = check1(s, i, i)) != null)
				return res;

		}
		return res;
	}