diff options
author | Jack Sangdahl <jack@pngu.org> | 2024-09-19 22:11:19 -0600 |
---|---|---|
committer | Jack Sangdahl <jack@pngu.org> | 2024-09-19 22:11:27 -0600 |
commit | e1681d1ad79dd6a2961fe04d24c1ed2152da161a (patch) | |
tree | 381aa71d95e40dc922d2962e64eaf1118fdc6095 | |
parent | 0e3a73d4a297707a2eba42ac8b1f4a04d63f1135 (diff) | |
download | leetcode-e1681d1ad79dd6a2961fe04d24c1ed2152da161a.tar.gz leetcode-e1681d1ad79dd6a2961fe04d24c1ed2152da161a.zip |
214. shortest palindrome
-rw-r--r-- | shortest_palindrome.c | 51 | ||||
-rw-r--r-- | shortest_palindrome.py | 25 |
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")) |