题目大意:给你一个字符串你可以在它的前面添加一些字符,返回最短的回文字符串。
Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.
For example:
Given "aacecaaa"
, return "aaacecaaa"
.
Given "abcd"
, return "dcbabcd"
.
Solution 1: Brute Force
Time complexity: O(n^2)
Space complexity: O(n)
C++ w/ copy
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 102 ms (<25.74%) class Solution { public: string shortestPalindrome(string s) { const string r(s.rbegin(), s.rend()); const int n = s.size(); for (int i = 0; i < n; ++i) if (s.substr(0, n - i) == r.substr(i)) return r.substr(0, i) + s; return ""; } }; |
C++ w/o copy
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua // Running time: 13 ms (<49.74%) class Solution { public: string shortestPalindrome(string s) { const string r(s.rbegin(), s.rend()); const int n = s.size(); for (int i = 0; i < n; ++i) if (s.compare(0, n - i, r, i, n - i) == 0) return r.substr(0, i) + s; return ""; } }; |