Leetcode 279: Perfect Squares

https://leetcode.com/problems/perfect-squares/

Code 1:

from collections import deque
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        q = deque()         
        visited = set()
        # val, step
        q.append((0,0))
        visited.add(0)

        while q:
            val, step = q.popleft()    
            for i in xrange(1, n+1):
                tmp = val + i**2
                if tmp > n:
                    break
                if tmp == n:
                    return step+1
                else:
                    if tmp not in visited:
                        visited.add(tmp)
                        q.append((tmp, step+1))                 
        
        # Should never reach here
        return -1   

 

Idea 1:

Use BFS to solve this problem. We can think of a tree graph in which nodes are value 0, 1,…,n. A link only exists between i and j (i<j) if j=i+square_num. We start from node 0 and add all nodes reachable from 0 to queue. Then we start to fetch elements from the queue to continue to explore until we reach node n. Since BFS guarantees that for every round all nodes in the queue have same depth, so whenever we reach node n, we know the least depth needed to reach n, i.e., the least number of square number to add to n.

Don’t forget to use a set `visited` to record which nodes have been visited. A node can be reached through multiple ways but BFS always makes sure whenever it is reached with the least steps, it is flagged as visited.

Why can’t we use DFS? Why can’t we report steps when we reach n by DFS? Because unlike BFS, DFS doesn’t make sure you are always using the least step to reach a node. Imagine DFS may traverse all nodes to reach n becaues each node is its previous node plus one (because one is a square number.) When you reach n, you use n steps. But it may or may not be the least number required to reach n.

This teaches us a lesson that if you want to find “….’s least number to do something”, you can try to think about solving it in BFS way.

 

Code 2:

import sys
import itertools
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # corner case 1
        if n < 0:
            return -1
        # corner case 2
        if n==0:
            return 1
    
        dp = [sys.maxint]*(n+1)
        dp[0] = 0

        for i in xrange(1, n+1):
            tmp = dp[i]
            for j in xrange(1, n+1):
                if j**2 > i:
                    break
                tmp = min(tmp, 1 + dp[i-j**2])
            dp[i] = tmp

        return dp[-1]

Idea 2:

Just normal DP. Leetcode actually reported TLE for this version. I guess it will pass if written in other language but with the same idea.

 

Reference

https://leetcode.com/discuss/57380/python-common-bfs-with-fewer-lines

https://docs.python.org/2/tutorial/datastructures.html