def numSquares(self, n):
queue = collections.deque([(0, 0)])
visited = set()
while queue:
i, step = queue.popleft()
step += 1
for j in xrange(1, n + 1):
k = i + j * j
if k > n:
break
if k == n:
return step
if k not in visited:
visited.add(k)
queue.append((k, step))
Python common BFS with fewer lines

Hi tusizi, why I rewrite your code a little bit as follow, it got TLE, could you help me to figure out the bottleneck here? I think the time complexity should be the same as your code. Thanks.
def numSquares(self, n): queue = collections.deque([(0, 0)]) visited = set() while queue: val, dis = queue.popleft() if val == n: return dis for i in xrange(1, n+1): j = val + i*i if j > n: break if j not in visited: visited.add(j) queue.append((j, dis+1))

@caikehe Your code need to clculate the whole level values ( "val +i*i") before you actually check whether get "n", more redundancy.
def numSquares(self, n): queue = collections.deque([(0, 0)]) visited = set() while queue: val, dis = queue.popleft() # if val == n: # return dis for i in xrange(1, n+1): j = val + i*i if j > n: break if j == n: return dis+1 if j not in visited: visited.add(j) queue.append((j, dis+1))