title: BFS solution to find least perfect squares
body: <p>I am working on a <a href="https://leetcode.com/problems/perfect-squares/" rel="nofollow noreferrer">Perfect Squares - LeetCode</a></p>
  
  <blockquote>
    <ol start="279">
    <li>Perfect Squares</li>
    </ol>
    
    <p>Given a positive integer <em>n</em>, find the least number of perfect square numbers (for example, <code>1, 4, 9, 16, ...</code>) which sum to <em>n</em>.</p>
    
    <p><strong>Example 1:</strong></p>
  
  <pre><code>Input: n = 12
  Output: 3 
  Explanation: 12 = 4 + 4 + 4.
  </code></pre>
    
    <p><strong>Example 2:</strong></p>
  
  <pre><code>Input: n = 13
  Output: 2
  Explanation: 13 = 4 + 9.
  </code></pre>
  </blockquote>
  
  <p>The key idea convert it to a find shortest path from n to 0 in a graph </p>
  
  <p><a href="https://i.stack.imgur.com/XKicE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XKicE.png" alt="enter image description here"></a></p>
  
  <p>A standard DFS solution </p>
  
  <pre><code>class Solution:
      def numSquares(self, n):
          """
          :type n: int
          :rtype: int
          """
          from collections import deque 
          #declare
          queue = deque()
          visited = set()
          #intitiate 
          step = -1
          queue.append(n)
          visited.add(n)
  
          while queue:
              step += 1
              size = len(queue)  
  
              for _ in range(size):
                  cur = queue.popleft()
                  if cur == 0: return step  #terminating checking 
  
                  #strech to collect next nodes 
                  i = 1
                  next_ = cur - i**2 #
                  while next_ &gt;= 0:
                      if next_ not in visited:
                          queue.append(next_)
                          visited.add(next_)
  
                      i += 1
                      next_  = cur - i**2
  </code></pre>
  
  <blockquote>
    <p>Runtime: 2532 ms, faster than 40.71% of Python3 online submissions for Perfect Squares.
    Memory Usage: 14 MB, less than 18.25% of Python3 online submissions for Perfect Squares.</p>
  </blockquote>
  
  <p>The part to collect next nodes  is not very concise </p>
  
  <pre><code>                #strech to collect next nodes 
                  i = 1
                  next_ = cur - i**2 #
                  while next_ &gt;= 0:
                      if next_ not in visited:
                          queue.append(next_)
                          visited.add(next_)
  
                      i += 1
                      next_  = cur - i**2
  </code></pre>
  
  <p>Tried to revise it as </p>
  
  <pre><code>            i = 1                  
              while  cur - i** 2 &gt;= 0:
                  next_ = cur - i ** 2:
                  if next_ not in visited:
                      queue.append(next_)
                      visited.add(next_)
                  i += 1
  </code></pre>
  
  <p>It worked but exceeded the time limitation.</p>
  
  <p>How could refactor that part?</p>