Month: October 2018

Link 931.Minimum Falling Path Sum

Thought

DFS

When first seeing this question, DFS prompt into my mind directly. Take Any node from first level as start, and search down stream. Until reach node in last level. For any path, it will have a value. Find the minimum value and it will be the answer

However, for any node, it has 3 paths -> go left lower, go right lower and go direct lower. So if I have N nodes per level, the time complexity is O(3^N) which cause TLE.

DP

Then, I find for any node, I dont quite care how it comes from the top level. What I do care is the minimum value, from any node at first level, pass level by level, then end at a specific node. So I don’t need to calculate again and again.

State Transfer Equation:
DP[i][j] = min(DP[i-1][j-1], DP[i-1][j], DP[i-1][j+1]) + Value[i][j]

Code

class Solution:
    def minFallingPathSum(self, A):
        """
        :type A: List[List[int]]
        :rtype: int
        """
        M = len(A)
        N = len(A[0])
        for i in range(1, M):
            for j in range(N):
                if j == 0:
                    A[i][j] = min(A[i-1][j], A[i-1][j+1]) + A[i][j]
                elif j == N - 1:
                    A[i][j] = min(A[i-1][j], A[i-1][j-1]) + A[i][j]
                else:
                    A[i][j] = min((A[i-1][j], A[i-1][j+1],A[i-1][j-1],)) + A[i][j]
        return min(A[-1])

Runtime

Time O(N^2)
Space O(N^2)

Link: Unique Email Addresses

Thought

Brutal Force Solution
This question is pretty simple (and it actually is an esay one). A naive approache is, split the name and domain.

For the name, remove every thing after first ‘+’, and then replace all ‘.’ as empty. For the domain, just keep it is.

Then, use a set to make sure every thing is unique. After processed all emails, count the length of the set.

Code

class Solution:
    def numUniqueEmails(self, emails):
        """
        :type emails: List[str]
        :rtype: int
        """
        hist = set()
        cnt = 0
        for email in emails:
            name, domain = email.split('@')
            name = name.split('+')[0]
            name=name.replace('.', '')
            if name + '@' + domain not in hist:
                hist.add(name+'@'+domain)
                cnt += 1
        return cnt

Runtime

Time: O(n)
Space: O(n)