题目大意：给你一个字符串你可以在它的前面添加一些字符，返回最短的回文字符串。
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 ""; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment