forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
next-palindrome-using-same-digits.cpp
46 lines (43 loc) · 1.21 KB
/
next-palindrome-using-same-digits.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Time: O(n)
// Space: O(1)
class Solution {
public:
string nextPalindrome(string num) {
if (!nextPermutation(begin(num), begin(num) + size(num) / 2)) {
return "";
}
copy(begin(num), begin(num) + size(num) / 2, rbegin(num));
return num;
}
private:
template<typename BidiIt>
bool nextPermutation(BidiIt begin, BidiIt end) {
const auto rbegin = reverse_iterator<BidiIt>(end);
const auto rend = reverse_iterator<BidiIt>(begin);
auto pivot = next(rbegin);
while (pivot != rend && *pivot >= *prev(pivot)) {
++pivot;
}
bool is_greater = true;
if (pivot != rend) {
auto change = find_if(rbegin, pivot, bind1st(less<int>(), *pivot));
swap(*change, *pivot);
} else {
is_greater = false;
}
reverse(rbegin, pivot);
return is_greater;
}
};
// Time: O(n)
// Space: O(1)
class Solution2 {
public:
string nextPalindrome(string num) {
if (!next_permutation(begin(num), begin(num) + size(num) / 2)) {
return "";
}
copy(begin(num), begin(num) + size(num) / 2, rbegin(num));
return num;
}
};