czxttkl

Code

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid: return 0
        
        m, n = len(grid), len(grid[0])
        # use 1D array as cache, initialized as 
        # the accumulated sum of first line
        dp = list(grid[0])
        for i in xrange(1, n):
            dp[i] += dp[i-1]
        
        for i in xrange(1, m):
            dp[0] += grid[i][0] 
            for j in xrange(1, n):
                dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
        
        return dp[-1]

Idea 

Use DP to solve this problem.If dp is a m*n 2D array, then `dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]`. As usual, the problem is in 2D but we only need to maintain a 1D cache, dp. When you scan each line of grid, dp actually represents the minimum path sum ending at each element of that line. 

Reference: https://discuss.leetcode.com/topic/15269/10-lines-28ms-o-n-space-dp-solution-in-c-with-explanations/2

Code

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        p1, p2, pt = m-1, n-1, m+n-1
        while p1 >= 0 and p2 >= 0:
            if nums2[p2] > nums1[p1]:
                nums1[pt] = nums2[p2]
                p2 -= 1
            else:
                nums1[pt] = nums1[p1]
                p1 -= 1
            pt -=1
        
        # no need to perform this loop. the remaining elements 
        # of nums1 will be there.
        # while p1 >= 0:
        #     nums1[pt] = nums1[p1]
        #     pt -= 1
        #     p1 -= 1
        
        while p2 >= 0:
            nums1[pt] = nums2[p2]
            pt -= 1
            p2 -= 1
        
        
        

Idea

Merge from end to start.

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Code

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.helper(range(1, 1+n), k, 0, path, res)
        return res
    
    def helper(self, l, k, start_idx, path, res):
        if k == 0:
            res.append(list(path))
            return 
        
        for i in xrange(start_idx, len(l)-k+1):
            path.append(l[i])
            self.helper(l, k-1, i+1, path, res) 
            path.pop()

Idea

What I use is backtracking dfs, which is a common algorithm applied in many questions, for example: https//nb4799.neu.edu/wordpress/?p=2416.

The parameters of helper function:

l: the original list containing 1 ~ n

path: the numbers already added into a temporary list 

k: how many numbers still needed to form a combination

start_idx: the next number to be added should be searched in the range from start_idx to end of the original list

res: the result list

Another elegant recursive solution: https://discuss.leetcode.com/topic/12537/a-short-recursive-java-solution-based-on-c-n-k-c-n-1-k-1-c-n-1-k

8 = 2 x 2 x 2;
  = 2 x 4.

[]

[]

[
  [2, 6],
  [2, 2, 3],
  [3, 4]
]

[
  [2, 16],
  [2, 2, 8],
  [2, 2, 2, 4],
  [2, 2, 2, 2, 2],
  [2, 4, 4],
  [4, 8]
]

Code

import math

class Solution(object):
    def getFactors(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        if n <= 1:
            return []
        res = []
        self.helper(n, 2, [], res)
        return res
        
    def helper(self, target, start_num, factors, res):
        if factors:
            res.append(list(factors)+[target])
         
        # only need to traverse until floor(sqrt(target))
        for i in xrange(start_num, int(math.sqrt(target))+1):
            if target % i == 0:
                factors.append(i)
                self.helper(target/i, i, factors, res)
                factors.pop()
                

Idea

Essentially a DFS. The parameters of the helper function:

target: the remaining factors should multiply to target

start_num: the remaining factors should be equal to or larger than start_num

factors: the factors so far, stored in a list

res: result

Reference: https://discuss.leetcode.com/topic/21082/my-recursive-dfs-java-solution

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Code

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        
        # convert to integer matrix
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                matrix[i][j] = int(matrix[i][j])
            
        max_size = max(matrix[0])
        # DP storage initialized with the first row of matrix
        vec = list(matrix[0])
        
        for row in xrange(1, len(matrix)):
            topleft = vec[0]
            vec[0] = matrix[row][0]
            
            for col in xrange(1, len(matrix[0])):
                if matrix[row][col] == 0:
                    new = 0
                else:
                    new = min(topleft, vec[col-1], vec[col]) + 1
                topleft = vec[col]
                vec[col] = new
            
            max_size = max(max_size, max(vec))
                
        return max_size * max_size
        
        
        

Idea

Think about it as a 2D DP problem. Suppose a list vec has size num_row * num_col. vec[i][j] is the size of the maximum square that can be achieved at matrix[i][j]. The core logic is that vec[i][j] = min(vec[i][j-1], vec[i-1][j],vec[i-1][j-1]). 

And we know that 2D DP problem can often be reduced to 1D. That’s how I implement currently.

Reference:

https://discuss.leetcode.com/topic/15328/easy-dp-solution-in-c-with-detailed-explanations-8ms-o-n-2-time-and-o-n-space

void addWord(word)
bool search(word)

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Code

class TrieNode():
    def __init__(self):
        self.nodes = {}
        self.isword = False
    
class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        root = self.root
        for i, ch in enumerate(word):
            if not root.nodes.get(ch, None):
                root.nodes[ch] = TrieNode()
            root = root.nodes[ch]
            if i == len(word) - 1:
                root.isword = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        assert len(word) > 0
        return self.search_helper(word, 0, self.root)
        
    def search_helper(self, word, idx, root):
        ch = word[idx]
        if ch == '.':
            if idx == len(word) - 1:
                 return any(map(lambda x: x.isword, root.nodes.values()))
            else:
                 return any(map(lambda x: self.search_helper(word, idx+1, x), root.nodes.values()))
        else:
            if root.nodes.get(ch, None) is None:
                return False
            else:
                if idx == len(word) - 1:
                    return root.nodes[ch].isword
                else:
                    return self.search_helper(word, idx+1, root.nodes[ch])
        
        

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

Idea

Use Trie structure to store words and make search. Assume we have O(N) words and each word has O(K) length. Then each add takes O(K) time and O(K) space. Each search takes O(K) time . See another post: https//nb4799.neu.edu/wordpress/?p=1162

https://leetcode.com/problems/meeting-rooms/

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def canAttendMeetings(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: bool
        """
        if not intervals or len(intervals) == 1:
            return True
        
        intervals = sorted(intervals, key=lambda x: x.start)
        
        for i in xrange(1, len(intervals)):
            if intervals[i].start < intervals[i-1].end:
                return False
        
        return True

Idea

You have to sort first which takes O(nlogn) time.

You can also look at the similar problem: https//nb4799.neu.edu/wordpress/?p=2205