# 906. Super Palindromes

Let’s say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers `L` and `R`(represented as strings), return the number of superpalindromes in the inclusive range `[L, R]`.

Example 1:

``````Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
``````

Note:

1. `1 <= len(L) <= 18`
2. `1 <= len(R) <= 18`
3. `L` and `R` are strings representing integers in the range `[1, 10^18)`.
4. `int(L) <= int(R)`

``````class Solution {
public:
int superpalindromesInRange(string L, string R) {
int res = 0;
long left = stol(L), right = stol(R);
helper("", left, right, res);
for (char c = '0'; c <= '9'; ++c) {
helper(string(1, c), left, right, res);
}
return res;
}
void helper(string cur, long& left, long& right, int& res) {
if (cur.size() > 9) return;
if (!cur.empty() && cur[0] != '0') {
long num = stol(cur);
num *= num;
if (num > right) return;
if (num >= left && isPalindrome(to_string(num))) ++res;
}
for (char c = '0'; c <= '9'; ++c) {
helper(string(1, c) + cur + string(1, c), left, right, res);
}
}
bool isPalindrome(string str) {
int left = 0, right = (int)str.size() - 1;
while (left < right) {
if (str[left++] != str[right--]) return false;
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/906

https://leetcode.com/problems/super-palindromes/

https://leetcode.com/problems/super-palindromes/discuss/170774/Java-building-the-next-palindrome

https://leetcode.com/problems/super-palindromes/discuss/171467/c%2B%2B-straightforward-backtracking-solution

https://leetcode.com/problems/super-palindromes/discuss/170779/Java-Concise-DFS-Solution-with-Explaination-No-Cheating

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation