aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <jack@pngu.org>2024-09-19 22:11:19 -0600
committerJack Sangdahl <jack@pngu.org>2024-09-19 22:11:27 -0600
commite1681d1ad79dd6a2961fe04d24c1ed2152da161a (patch)
tree381aa71d95e40dc922d2962e64eaf1118fdc6095
parent0e3a73d4a297707a2eba42ac8b1f4a04d63f1135 (diff)
downloadleetcode-e1681d1ad79dd6a2961fe04d24c1ed2152da161a.tar.gz
leetcode-e1681d1ad79dd6a2961fe04d24c1ed2152da161a.zip
214. shortest palindrome
-rw-r--r--shortest_palindrome.c51
-rw-r--r--shortest_palindrome.py25
2 files changed, 76 insertions, 0 deletions
diff --git a/shortest_palindrome.c b/shortest_palindrome.c
new file mode 100644
index 0000000..e68beaa
--- /dev/null
+++ b/shortest_palindrome.c
@@ -0,0 +1,51 @@
+// 214. Shortest Palindrome
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+char *shortestPalindrome(char *s) {
+ int n = strlen(s), dropped, right = 0, left = 0;
+ int *lut = (int *)malloc((n >> 1) * sizeof(int));
+ char *ans = (char *)malloc((n << 1) * sizeof(char));
+ if (n < 2)
+ return s;
+ lut[right++] = 0;
+ while (right < n >> 1) {
+ if (s[right] == s[left])
+ lut[right++] = ++left;
+ else if (!left)
+ lut[right++] = left;
+ else
+ left = lut[--left];
+ }
+ dropped = left = 0;
+ right = --n;
+ while (left < right)
+ if (s[left] == s[right]) {
+ left++;
+ right--;
+ } else if (left && lut[left - 1]) {
+ left = lut[--left];
+ dropped = n - right - left;
+ } else {
+ left = 0;
+ right--;
+ dropped = n - right;
+ }
+ free(lut);
+ for (left = 0; left < dropped; left++)
+ ans[left] = s[n - left];
+ for (left, right = 0; right <= n; left++, right++)
+ ans[left] = s[right];
+ ans[left] = '\0';
+ return ans;
+}
+int main() {
+ char *s1 = "aacecaaa", *s2 = "abcd";
+ printf("%s\n", shortestPalindrome(s1)); // expect: aaacecaaa
+ printf("%s\n", shortestPalindrome(s2)); // expect: dcbabcd
+}
diff --git a/shortest_palindrome.py b/shortest_palindrome.py
new file mode 100644
index 0000000..48f2306
--- /dev/null
+++ b/shortest_palindrome.py
@@ -0,0 +1,25 @@
+# 214. Shortest Palindrome
+
+"""
+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.
+"""
+
+
+class Solution(object):
+ def shortestPalindrome(self, s):
+ """
+ :type s: str
+ :rtype: str
+ """
+ r = s[::-1]
+ for i in range(len(s) + 1):
+ if s.startswith(r[i:]):
+ return r[:i] + s
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.shortestPalindrome("aacecaaa"))
+ print(obj.shortestPalindrome("abcd"))