Leetcode Shortest Palindrome problem solution YASH PAL, 31 July 2024 In this Leetcode Shortest Palindrome problem solution, You are given a string s. You can convert s to a palindrome by adding characters in front of it. Return the shortest palindrome you can find by performing this transformation. Problem solution in Python. class Solution(object): def shortestPalindrome(self, s): prefix_idx = 0 for i in range(len(s)-1, -1, -1): if s[i] == s[prefix_idx ]: prefix_idx += 1 if prefix_idx == len(s): return s suffix = s[prefix_idx:] return suffix[::-1] + self.shortestPalindrome(s[:prefix_idx]) + suffix Problem solution in Java. class Solution { public String shortestPalindrome(String s) { String temp = s + "#" + new StringBuilder(s).reverse().toString(); int[] next = getTable(temp); return new StringBuilder(s.substring(next[next.length - 1] + 1)).reverse().toString() + s; } public int[] getTable(String s) { int[] next = new int[s.length()]; next[0] = -1; int k = -1; int j = 0; while (j < s.length() - 1) { if (k == -1 || s.charAt(j) == s.charAt(k)) { j++; k++; next[j] = k; } else { k = next[k]; } } return next; } } Problem solution in C++. class Solution { public: string shortestPalindrome(string s) { string rev_s = s; reverse(rev_s.begin(), rev_s.end()); string l = s + "#" + rev_s; vector<int> p(l.size(), 0); for (int i = 1; i < l.size(); i++) { int j = p[i - 1]; while (j > 0 && l[i] != l[j]) j = p[j - 1]; p[i] = (j += l[i] == l[j]); } return rev_s.substr(0, s.size() - p[l.size() - 1]) + s; } }; Problem solution in C. bool findLongest(char *s, int len, int index1, int index2, int *remain) { while (index1 >= 0 && index2 <= len - 1 && s[index1] == s[index2]) { index1--; index2++; } if (index1 == -1 && *remain > len - index2) { *remain = len - index2; return true; } return false; } char * shortestPalindrome(char * s){ int index = 0, len = strlen(s); int remain = len - 1, new_len = 2 * len - 1; if (len == 0) return calloc(1, sizeof(char)); for (int i=len/2; i>=0; --i) { if (findLongest(s, len, i - 1, i + 1, &remain)) break; if (findLongest(s, len, i - 1, i , &remain)) break; } new_len = len + remain; char *result = (char*)malloc(sizeof(char) * (new_len + 1)); for (int i=0; i<remain; i++) { result[i] = s[len - i - 1]; } for (int i=0; i<len; i++) { result[remain + i] = s[i]; } result[new_len] = 0; return result; } coding problems