# 906. Super Palindromes 超级回文数

@TOC

## # 题目描述

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)`

## # 解题方法

### # BFS解法

``````# n, n^2
(1, 1)
(2, 4)
(3, 9)
(11, 121)
(22, 484)
(101, 10201)
(111, 12321)
(121, 14641)
(202, 40804)
(212, 44944)
(1001, 1002001)
(1111, 1234321)
(2002, 4008004)
``````

``````class Solution:
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
que = collections.deque(["11", "22"])
candi = set()
while que:
size = len(que)
for _ in range(size):
p = que.popleft()
if int(p) ** 2 > int(R):
continue
for j in ["0", "1", "2"]:
q = (p[:len(p)//2] + j + p[len(p)//2:])
que.append(q)
res = 0
for cand in candi:
if int(L) <= int(cand) ** 2 <= int(R) and self.isPalindromes(int(cand) ** 2):
res += 1
return res

def isPalindromes(self, s):
s = str(s)
N = len(s)
for l in range(1, N // 2):
if s[l] != s[N - 1 - l]:
return False
return True
``````

## # 参考资料

https://leetcode.com/problems/super-palindromes/discuss/171450/Python-AC-bfs-detail-explanation

## # 日期

2018 年 11 月 3 日 —— 雾霾的周六