Mi Favorite LeetCode Hard Problems and How to Solve Them (1)

Index

#44 [Dynamic Programming]
#60 [Math, Recursion]
#632 [Heap]

#44 : Wild Card Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Solution using Dynamic Programming:

class Solution:
    def isMatch(self, s: str, p: str) -> bool:

        if p == '':
            return s == ''


        # first get rid of all the extra "*"s because "*" is equiv to "**"
        def clear_pattern(p):
            ans = []
            for i in range(len(p)):
                if p[i] != '*':
                    ans.append(p[i])
                else:
                    if ans and ans[-1] == '*':
                        continue
                    else:
                        ans.append(p[i])
            p = ''.join(ans)
            return p
        p = clear_pattern(p)

        
        # set up dynamic programming. dp[i][j] = 1 meaning p[:j] matches s[:i]
        dp = [[0 for k in range(len(p)+1)] for k in range(len(s)+1)]
        

        # initialize
        dp[0][0] = 1
       
        if p[0] == '*':
            dp[0][1] = 1


        for j in range(1,len(p)+1): # use pattern as outer loop
            for i in range(1,len(s)+1):

                if p[j-1] == '*': # case 1
                    if dp[i-1][j-1] == 1:
                        dp[i][j] = 1
                    if dp[i][j-1] == 1:
                        dp[i][j] = 1
                    if dp[i-1][j] == 1:
                        dp[i][j] = 1

                elif p[j-1] in [s[i-1],'?']: # case 2
                    if dp[i-1][j-1] == 1:
                        dp[i][j] = 1
              
                else: # case 3
                    pass
                    
    
        return dp[-1][-1] == 1

Brief explanation:

We are building a table of the state space. dp[i][j] indicates whether the string and pattern are matched up to, respectively, ith and jth character.

dp[i][j] is decided by the s[i-1], p[j-1] and the "adjacent states". 

1. If p[j-1] is not a wild card or s[i-1], dp[i][j] = 0 in ANY circumstance. (case 3)

2. If p[j-1] is '?' or s[i-1]: dp[i][j] = d[i-1][j-1], because if the previous string and patterns don't match, then there is no point matching the current one. (case 2)

1. p[j-1] = '*' is the most complicated case because "*" can correspond to 0-n characters. There are a couple situations. (case 1)
  a. "*" <=> ''. Then, if dp[i][j-1] == 1, dp[i][j] = 1. 
  b. "*" <=> more than one character. That means if dp[i-1][j] = 1, dp[i][j] = 1
  c. same as case 2.

*Note that in 1.b it's actually "if dp[i-k][j] = 1", but since the table is constructed recursively, we don't have to "look back".

>>> Back to the top

#60: Permutation Sequence

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence n = 3:

"123"
 "132"
 "213"
 "231"
 "312"
 "321"
Given n and k, return the kth permutation sequence.

The only key to solve this problem is just math intuition, and this is why I like it. Hehe.

import math

class Solution:
    def getPermutation(self, n: int, k: int) -> str:

        # This is essentially a math question.
        # the first digit = (k-1)//(# permutation of the numbers left) + 1
        # the rest is euclidean algorithm.
        
        num_set = [i+1 for i in range(n)]
 
        if n == 1 and k == 1:
            return '1'

        output = ''
        div = k
        for i in range(n):
            num = n-i
            n_perm = math.factorial(num-1)
            #print(n_perm, div)
            select = num_set[(div-1)//n_perm]
            num_set.pop((div-1)//n_perm)
            output += str(select)
            div = div%n_perm

        return output

Brief Explanation: 

First go through several observations.
1. # permutation of n numbers  = n!, because the first spot has n choices, the second has n-1, and so on and so on. Therefore, there are (n-1)! permutation with each leading number.

2. The permutations are ordered lexicographically. This means that we can understand it as a carry system (Binary, Decimal, etc...) the preceding digit get +1 onces its following digit hits n. The first digit thus +1 every (n-1)!, the second digit every (n-2)! ...

>>> Back to the top

#632 Smallest Range Covering Element….

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Solution using heapq (highly suggest to use the built-in because this thing is tree structured how are you gonna write it on spot?)

import heapq

class Solution:
    def smallestRange(self, nums):
        """
        :type nums: List[List[int]]
        :rtype: List[int]
        """ 
        heap = [(List[0], index, 0) for index, List in enumerate(nums)]  

        heapq.heapify(heap)                                              
        
        max_val = max([List[0] for List in nums])                        
        smallest_range = float(-inf), float(if)                                      
        
        while heap:
            min_val, list_index, num_index = heapq.heappop(heap)         
            
            if max_val - min_val < smallest_range[1] - smallest_range[0]:  
                smallest_range = min_val, max_val
                
            if num_index + 1 == len(nums[list_index]):                   
                return smallest_range
            
            next_num = nums[list_index][num_index+1]                     
            
            max_val = max(max_val, next_num)
            heapq.heappush(heap, (next_num, list_index, num_index+1))

Leave a Reply Cancel reply