LeetCode Classic Problems

01LeetCode 1: Two Sum

Source notebook: 001._two_sum.ipynb

1. Two Sum

Problem:

• https://leetcode.com/problems/two-sum/
• https://leetcode-cn.com/problems/two-sum/description/

Given an array of integers and a target value, find the two numbers in the array that add up to the target.

You may assume that each input has exactly one solution, and the same element may not be used twice.

> Example:

Given nums = [2, 7, 11, 15], target = 9

Because nums[0] + nums[1] = 2 + 7 = 9
we return [0, 1]

Difficulty: Easy

This problem is fairly easy; the only thing to watch out for is that the same element may not be used twice.

It is also worth asking: can we find the two numbers with a single pass through the array?

Let's look at how to solve this problem.

Approach 1

• Simply check whether both numbers are in the list, making sure the two numbers are not the same element reused.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # loop over the list nums
        for num_one in nums:
            # check whether target - num_one is also in nums, and that the two numbers are not the same element
            if target - num_one in nums and num_one is not target-num_one:
                # return the indices of the two numbers
                return [nums.index(num_one), nums.index(target - num_one)]
            
nums = [4, 3, 5, 15]
target = 8
s = Solution()
print(s.twoSum(nums, target))

[1, 2]

Approach 2

• The previous solution already used a single for loop; this time let's change the idea.
• A brute-force $O(n^2)$ double loop would work (lookup).
• But we can also trade space for time — a remarkably clever accepted (AC) solution.

    2         7        11    15
    not seen  found
lookup {2:0} [0, 1]

The overall idea:

• Build a dictionary lookup that stores each number we have seen along with its index.
• For the current number, check whether target - current number already exists in lookup; if it does, the stored value and the current value sum to target.
• If it exists, return the index of target - current number and the index of the current value.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # create the lookup dictionary
        lookup = {}
        # enumerate yields each element together with its index
        for i, num in enumerate(nums):
            if target - num in lookup:
                return [lookup[target - num],i]
            lookup[num] = i
        return []
    
nums = [4, 3, 5, 15]
target = 8
s = Solution()
print(s.twoSum(nums, target))

[1, 2]

Approach 3

• A dict (a "map" in other languages) answers membership queries via hashing without scanning, whereas a list must be traversed element by element — sets and dicts are much faster for in checks.
• We can mimic the code above but write it more simply.
• With the dictionary approach, just checking whether i and target - i are equal values is wrong: if two elements have the same value but are different elements, the naive check breaks.

For example, let's first look at the incorrect version:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict1 = {}
        for k, i in enumerate(nums):
            dict1[i] = k
            if target - i in dict1 and i is not target - i:
                return [dict1[target - i], dict1[i]]

nums = [3, 3]
target = 6
s = Solution()
print(s.twoSum(nums, target))

None

The code above is buggy: for identical elements [3, 3] with target = 6 it returns None, although it should return [0, 1]. So the membership check there is incorrect.

• With the dictionary approach we must key by value and store the index as the value; a naive "in or not in" check alone effectively adds another pass.

The version below is the correct one:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for k, i in enumerate(nums):
            if target - i in nums[k + 1:]:
                return [k, nums[k + 1:].index(target - i) + k + 1]

nums = [3, 3]
target = 6
s = Solution()
print(s.twoSum(nums, target))       

[0, 1]

Summary

There are certainly even better solutions out there — contributions are welcome. Here's to good work and a good future!

02LeetCode 2: Add Two Numbers

Source notebook: 002._add_two_numbers.ipynb

2. Add Two Numbers

Difficulty: Medium

Problem:

Original links:

• Chinese: https://leetcode-cn.com/problems/add-two-numbers/description/
• English: https://leetcode.com/problems/add-two-numbers/

Description:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Add the two numbers and return the sum as a new linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input:  (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Reason: 342 + 465 = 807

Solutions

Since adding two digits can produce a carry, the addition itself is trivial — the key point is to account for the carry from the previous digit and propagate it into the next digit's computation.

Approach 1

We first create an empty (dummy) head node that stays fixed, and grow the list by appending new nodes at the tail. Traverse the common part of both lists, at each step adding the corresponding digits plus the carry and appending the result to the output list. After the common part is exhausted, process the remainder of the longer list the same way.

• Note that the carry must be updated on every step, checking whether the current sum overflows, to avoid polluting the following digits.
• In Python we need fresh cursor variables to walk the two lists; do not advance the parameters directly, or we would mutate the original lists.
• Don't forget a possible final carry at the end.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:     
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # assign p1, p2 = l1, l2 so our operations don't mutate the original lists
        p1, p2 = l1, l2
        # create an empty list for the result, with a head node and a tail node
        head = ListNode(0)
        tail = head
        # carry holds the carry value
        carry = 0
        # process the common part of the two lists, i.e. while both are non-empty
        while p1 and p2:
            # sum of the current digits
            num = p1.val + p2.val + carry
            # greater than 9 -> carry one into the next digit
            if num > 9:
                num -= 10
                carry = 1
            else:
                carry = 0
            # append a node
            tail.next = ListNode(num)
            # advance the tail node
            tail = tail.next
            # advance both lists in their common part
            p1 = p1.next
            p2 = p2.next
        # take the remainder of the longer list, not yet processed above
        if p2:
            # if p2 is longer, assign its remainder to p1 so we only have to handle p1
            p1 = p2
        # now process the remainder of the longer list
        while p1:
            # for this digit, remember to account for a possible carry
            num = p1.val + carry
            if num > 9:
                num -= 10
                carry = 1
            else:
                carry = 0
            # append a node
            tail.next = ListNode(num)
            tail = tail.next
            
            # advance the list we are processing
            p1 = p1.next
        # if a carry remains at the end, allocate one more node
        if carry:
            # create a ListNode with val 1, then advance the tail
            tail.next = ListNode(1)
            tail = tail.next
        # all sums and carries handled; terminate the list
        tail.next = None
        # return the head of the list
        return head.next # drop the dummy head node initialized to 0

la = ListNode(2)
la.next = ListNode(4)
la.next.next = ListNode(3)

lb = ListNode(5)
lb.next = ListNode(6)
lb.next.next = ListNode(4)

s = Solution()
ss = s.addTwoNumbers(la, lb)
print(ss.val)
print(ss.next.val)
print(ss.next.next.val)
print(ss.next.next.next) 

7
0
8
None

Therefore we can also solve this recursively, breaking it into the following cases:

• When both lists are non-empty: compute the sum of the two node values plus the incoming carry; build a new node from the ones digit of the sum, set the carry to the tens digit, and point this node's next at the node returned by recursing on the next digits.
• When exactly one list is empty: compute the sum of the non-empty node's value plus the carry, and update the carry to the tens digit. If the carry is non-zero, build a new node from the ones digit and point its next at the result of recursing further (passing only the non-empty list). If the carry is zero, simply set the non-empty node's value to the sum — no higher digits can change anymore — and return that node.
• When both lists are empty: if the carry is 0, return NULL; otherwise build a new node holding the carry and return it.

Approach 2

• The same trick as in Plus One and Add Binary, but compared with the previous approach it is simpler and more concise.
• Recursion keeps the algorithm short.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        # special cases
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        # if the sum is less than 10, no carry is needed
        if l1.val + l2.val < 10:
            l3 = ListNode(l1.val + l2.val)
            l3.next = self.addTwoNumbers(l1.next, l2.next)
        # sum is 10 or more: carry needed
        elif l1.val + l2.val >= 10:
            l3 = ListNode(l1.val + l2.val - 10)
            tmp = ListNode(1)
            tmp.next = None
            # recursive call
            l3.next = self.addTwoNumbers(l1.next, self.addTwoNumbers(l2.next ,tmp))
        return l3
    
la = ListNode(2)
la.next = ListNode(4)
la.next.next = ListNode(3)

lb = ListNode(5)
lb.next = ListNode(6)
lb.next.next = ListNode(4)

s = Solution()
ss = s.addTwoNumbers(la, lb)
print(ss.val)
print(ss.next.val)
print(ss.next.next.val)
print(ss.next.next.next)

7
0
8
None

03LeetCode 5: Longest Palindromic Substring

Source notebook: 005._longest_palindromic_substring.ipynb

005. Longest Palindromic Substring

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/longest-palindromic-substring/description/
• English: https://leetcode.com/problems/longest-palindromic-substring/

Description

Given a string s, find the longest palindromic substring in s. You may assume the maximum length of s is 1000.

Example 1:
Input:  "babad"
Output: "bab"
Note:   "aba" is also a valid answer.

Example 2:
Input:  "cbbd"
Output: "bb"

Solutions

Approach 1

A string that reads the same left-to-right and right-to-left is called a palindrome, e.g. aba or abba.

The first idea is the most naive one: treat each character in turn as the center of a palindrome and expand outward in both directions, finding the longest palindrome centered at that character. This requires handling odd-length and even-length palindromes separately. The next key detail is boundary handling — make sure indices never go out of range. When the substring already includes the first or last character and is still a palindrome, the indices step one position past each edge and must be compensated for.

Take abba as an example: it has an even number of characters, and the 1st equals the last, the 2nd equals the 2nd-from-last, ..., the Nth equals the Nth-from-last.

Take aba as an example: it has an odd number of characters; excluding the middle character, the 1st equals the last, ..., the Nth equals the Nth-from-last.

So, having found a candidate substring of length len1, we test whether it satisfies: 1st char = last char, 2nd = 2nd-from-last, ..., Nth = Nth-from-last — i.e. we compare characters pairwise from both ends toward the middle. If after [length/2] comparisons all pairs match (the i-th equals the i-th from the end), the substring must be a palindromic string. And clearly this holds whether the length is odd or even, since for odd lengths the middle character trivially equals itself.

The problem thus reduces to finding a substring whose first character equals its last character (call it a candidate substring), and then checking the remaining characters.

Let's look at the code below:

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return
        n = len(s)
        if n == 1:
            return s
        # Left index of the target substring
        l = 0
        # Right index of the target substring
        r = 0
        # Length of the longest palindromic substring for now 
        m = 0
        # Length of the current substring
        c = 0
        # Whether the substring contains the first character or last character
        # and is palindromic
        b = True
        # i indexes a character of the string
        for i in range(0, n):
            # odd-length case
            # j tests whether the j characters on both sides of position i form a palindrome; n-i keeps us inside the end of the string, i+1 keeps us from crossing the start
            for j in range(0, min(n - i, i + 1)):
                # expanding around center i: if characters differ, it is not a palindrome, stop comparing
                if (s[i - j] != s[i + j]):
                    b = False
                    break
                else:
                    # if expanding j characters around center i is a palindrome, record its current length in c
                    c = 2 * j + 1
            # compare c with m, the longest palindrome length so far; if c > m, take c as the new longest length, otherwise keep m
            if (c > m):
                # set the new palindrome's left index; b is True == 1, False == 0
                l = i - j + 1 - b
                # set the new palindrome's right index
                r = i + j + b
                # store the new longest palindrome length in m
                m = c
            b = True
            # even-length case
            # i+1 keeps us from crossing the start of the string, n-i-1 from passing its end
            for j in range(0, min(n - i - 1, i + 1)):
                # even case: if the mirrored positions match it is a palindrome, otherwise it is not
                if (s[i - j] != s[i + j + 1]):
                    b = False
                    break
                else:
                    c = 2 * j + 2
            if (c > m):
                l = i - j + 1 - b
                r = i + j + 1 + b
                m = c
            b = True
        # return the final palindrome
        return s[l:r]
    
s = Solution()
nums = "acbcd"
print(s.longestPalindrome(nums))

cbc

The code above is our reference version — the logic is quite clear. The version below is Lisanaaa's polished revision of it; the overall idea is the same, so feel free to compare the two.

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        n = len(s)

        m,l,r = 0,0,0

        for i in range(n):
            # odd case
            for j in range(min(i+1,n-i)):
                if s[i-j] != s[i+j]:
                    break
                if 2*j + 1 > m :
                    m = 2 * j + 1
                    l = i-j
                    r = i+j


            if i+1 < n and s[i] == s[i+1]:
                for j in range(min(i+1,n-i-1)):
                    if s[i-j] != s[i+j+1]:
                        break
                    if 2 * j + 2 > m :
                        m = 2*j +2
                        l = i-j
                        r = i+j+1


        return s[l:r+1]
    
s = Solution()
nums = "acbcd"
print(s.longestPalindrome(nums))

cbc

Approach 2

This is an obvious dynamic-programming idea.

• This problem is related to the dynamic-programming problems we did before — specifically problem 72 (Edit Distance); the idea is the same, but compared with problem 72 this one is much simpler.
• A nice observation: the longest substring shared by s and reverse(s) is the longest palindromic substring — which turns the task into a Longest Common Substring problem.
• Look at the code below and it will make sense.
• If it still isn't clear, read our write-up of problem 72, which explains it thoroughly.

class Solution2(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def lcs(s1, s2):
            m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
            longest, x_longest = 0, 0
            for x in range(1, 1 + len(s1)):
                for y in range(1, 1 + len(s2)):
                    if s1[x - 1] == s2[y - 1]:
                        m[x][y] = m[x - 1][y - 1] + 1
                        if m[x][y] > longest:
                            longest = m[x][y]
                            x_longest = x
                    else:
                        m[x][y] = 0
            return s1[x_longest - longest: x_longest]

        return lcs(s, s[::-1])
    
s_2 = Solution2()
nums = "acbcd"
print(s_2.longestPalindrome(nums))

cbc

A classic dynamic-programming problem.

Pseudocode:

LCSuff(S1...p, T1...q) = LCS(S1...p1, T1...q-1) if S[p] = T[q] else 0

Reference implementation:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring#Python_2

However, the dynamic-programming solution above still times out.

We assumed that s[::-1] alone would be fast enough.

Important caveat:

This method is buggy. Consider the string abcxgcba: reversed it is abcgxcba. The two share a common substring, yet it contains no palindrome. The fix:

we check if the substring's indices are the same as the reversed substring's original indices. If it is, then we attempt to update the longest palindrome found so far; if not, we skip this and find the next candidate.

My take on the fix:

original  reversed
ABXYBA    ABYXBA

The computed substring indices are 0:2, but s1[0:2] and s2[0:2] are identical positions, so it fails.
Likewise the common substring indices s[4:6] and s2[4:6] coincide — also invalid.

Whereas for ABAD and DABA:

the substring indices are 0:3 in one and 1:4 in the other, so there is no problem.

Approach 3

Manacher's algorithm (nicknamed the "race car" algorithm from its Chinese homophone)

Manacher's algorithm adds two auxiliary variables id and mx, where id is the center of the longest palindromic substring found so far and mx = id + P[id] — i.e. the right boundary of that palindrome. The key result:

• If mx > i, then P[i] >= Min(P[2 * id - i], mx - i). Here is why.

Let j = 2 * id - i, i.e. j is the mirror of i about id.

• When mx - i > P[j], the palindrome centered at S[j] is contained inside the palindrome centered at S[id]; since i and j are symmetric, the palindrome centered at S[i] must also be contained inside the palindrome centered at S[id], so P[i] = P[j].

• When P[j] >= mx - i, the palindrome centered at S[j] need not be fully contained in the palindrome centered at S[id]. By symmetry, though, the two mirrored regions are identical, so the palindrome centered at S[i] extends right at least to mx, i.e. P[i] >= mx - i. Whether it extends past mx must be checked by explicit matching. Hence P[i] >= Min(P[2 * id - i], mx - i): the left boundary of the palindrome centered at j may extend past the mirror of mx about id, in which case we can only guarantee P[i] = P[2 * id - i].

• Additionally, when mx <= i, we cannot assume anything about P[i]; set P[i] = 1 and match outward explicitly.

In the program below my P array stores, for each character taken as a palindrome center, the length of that palindrome (excluding the center character itself).

A small example: for the original string 'qacbcaw' the longest palindromic substring is obviously 'acbca'.

So in the final code, max_i is index 8 corresponding to character 'b', start = (max_i - P[max_i] - 1) / 2 = 1, and the final output is s[1:6], i.e. 'acbca'.

class Solution3(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        def preProcess(s):
            if not s:
                return ['^', '&']
            T = ['^']
            for i in s:
                T += ['#', i]
            T += ['#', '$']
            return T
        T = preProcess(s)
        P = [0] * len(T)
        id, mx = 0, 0
        for i in range(1, len(T)-1):
            j = 2 * id - i
            if mx > i:
                P[i] = min(P[j], mx-i)
            else:
                P[i]= 0
            while T[i+P[i]+1] == T[i-P[i]-1]:
                P[i] += 1
            if i + P[i] > mx:
                id, mx = i, i + P[i]
        max_i = P.index(max(P))    # index of the center of the longest palindromic substring
        start = int((max_i - P[max_i] - 1) / 2)
        res = s[start: start + P[max_i]]
        return res
    
s_3 = Solution3()
nums = "acbcd"
print(s_3.longestPalindrome(nums))   

cbc

When you run the code, the result may differ from the expected output, but both answers are valid for that input, so submit with confidence. Also check out problem 647, which can be solved with the same algorithm.

04LeetCode 7: Reverse Integer

Source notebook: 007._Reverse_Integer.ipynb

7. Reverse Integer

Difficulty: Easy

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/reverse-integer/description/
• English: https://leetcode.com/problems/Reverse-Integer

Description

Given a 32-bit signed integer, reverse its digits.

Example 1:
Input:  123
Output: 321

Example 2:
Input:  -123
Output: -321

Example 3:
Input:  120
Output: 21

Note:
Assume the environment can only store 32-bit signed integers, whose range is [-2^31, 2^31 - 1]. Under this assumption, return 0 when the reversed integer overflows.

Solutions

Approach 1

• x > 0 means flag = 1; x < 0 means flag = -1.
• Convert x to a string s = str(abs(x)), then reverse the string: s1 = s[::-1].
• Convert the string back to an integer: x1 = int(s1) * flag.
• Check for overflow and return the result.

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        # for negatives, remember to work with the absolute value
        flag = 1
        x_1 = 0
        if x < 0:
            flag = -1
            x = int(str(abs(x))[::-1])
            x_1 = x * flag
        else:
            flag = 1
            x = int(str(x)[::-1])
            x_1 = x * flag
        if x_1 > 2**31-1 or x_1 < -2**31:
            return 0
        else:
            return x_1

s = Solution()
x = 120
y = -456
print(s.reverse(x))
print(s.reverse(y))

21
-654

Approach 2

• Peel digits off the low end and re-attach them at the high end.
• In a loop, take the last digit each time (modulo), then integer-divide the original number by 10 — yielding one ones-digit per iteration.
• Reverse the operation: multiply the accumulator by 10 and add each extracted digit, which produces the reversed number.
• One caveat: in Python the result of the modulo operation takes the sign of the divisor, e.g. 5 % 2 = 1 but 5 % (-2) = -1.

class Solution:
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        num = 0
        flag = 1
        if x > 0:
            flag = 1
        else:
            flag = -1
        while x != 0:
            num = num * 10 + x % (10 * flag)
            x = int(x / 10)
        if num > 2**31-1 or num < -2**31:
            return 0
        else:
            return num
s = Solution()
x = 120
y = -456
print(s.reverse(x))
print(s.reverse(y))

21
-654

05LeetCode 9: Palindrome Number

Source notebook: 009._Palindrome_Number.ipynb

9. Palindrome Number

Difficulty: Easy

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/palindrome-number/description
• English: https://leetcode.com/problems/palindrome-number

Description

Determine whether an integer is a palindrome. A palindrome reads the same forward (left to right) and backward (right to left).

Example 1:

Input:  121
Output: true

Example 2:

Input:  -121
Output: false
Explanation: read left to right it is -121; read right to left it is 121-. Therefore it is not a palindrome.

Example 3:

Input:  10
Output: false
Explanation: read right to left it is 01. Therefore it is not a palindrome.

Follow-up:

Can you solve it without converting the integer to a string?

Solutions

Approach 1

• First, a negative number can never be a palindrome.
• Reverse via string conversion, convert back to a number, and compare for equality.

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        # negatives are never palindromes; rule them out
        if x < 0:
            return False
        # convert to str, reverse, convert back to int and compare: equal means palindrome, unequal means not
        elif x != int(str(x)[::-1]):
            return False
        else:
            return True
        
s = Solution()
x = 2345
y = 121
print(s.isPalindrome(x))
print(s.isPalindrome(y))

False
True

Approach 2

• A negative number is never a palindrome.
• If a number is positive and divisible by 10, it cannot be a palindrome either.
• This lets us cut the work down.

class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        # handle special cases:
        # 1. negatives are never palindromes
        # 2. if the last digit is 0, the first digit would also have to be 0 for a palindrome; only 0 itself qualifies
        if x < 0 or (x % 10 == 0 and x is not 0):
            return False
        revertNumber = 0
        while x > revertNumber:
            revertNumber = revertNumber * 10 + x % 10
            x /= 10
        # when the digit count is odd, revertedNumber/10 removes the middle digit.
        # e.g. for input 12321, at the end of the while loop x = 12 and revertedNumber = 123;
        # the middle digit never affects palindromicity (it always equals itself), so we can simply drop it.
        return x == revertNumber or x == revertNumber/10

s = Solution()
x = 2345
y = 121
print(s.isPalindrome(x))
print(s.isPalindrome(y))

False
True

06LeetCode 10: Regular Expression Matching

Source notebook: 010._regular_expression_matching.ipynb

010. Regular Expression Matching

Difficulty: Hard

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/two-sum/description
• English: https://leetcode.com/problems/two-sum

Description

Given an input string (s) and a pattern (p), implement regular-expression matching with support for '.' and '*'.

'.' matches any single character.
'*' matches zero or more of the preceding element.
The match must cover the entire input string (s), not a partial substring.

Notes:
 - s may be empty and contains only lowercase letters a-z.
 - p may be empty and contains only lowercase letters a-z plus the characters . and *.

Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" cannot match the whole string "aa".

Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' matches zero or more of the preceding element, 'a'. Repeating 'a' once gives "aa".

Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" matches zero or more ('*') of any character ('.').

Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: 'c' can be repeated zero times and 'a' repeated once, matching "aab".

Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false

Solutions

Approach 1

Brute force. Credit to Lisanaaa for working this one out — I'd racked my brain over a brute-force solution without covering all the cases. Let's see how he solved it.

"." is easy to handle. The hard part is "": it never appears alone — it always pairs with the preceding letter or ".". Viewed as a pair "X", its behavior is: match zero occurrences, or match a run of consecutive "X". A useful trick for the brute-force attempt is to match from the back toward the front.

The brute-force solution does get accepted (AC).

Case analysis:

• If s[i] = p[j] or p[j] = '.': advance the match by one position.
• If p[j] = '': check whether p[j-1] = '.' or p[j-1] = s[i]; if so, try advancing the match — if that succeeds, return True. Otherwise skip the whole 'X'. Pay attention to the recurrence here.
• Then handle the boundary cases:
• s is fully matched but p still has characters left: the remainder can still match if it consists of X*-style pairs, so check for that.
• p is exhausted but s still has unmatched characters: return False.

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        def helper(s, i, p, j):
            if j == -1:
                return i == -1
            if i == -1:
                if p[j] != '*':
                    return False
                return helper(s, i, p, j-2)
            if p[j] == '*':
                if p[j-1] == '.' or p[j-1] == s[i]:
                    if helper(s, i-1, p, j):
                        return True
                return helper(s, i, p, j-2)
            if p[j] == '.' or p[j] == s[i]:
                return helper(s, i-1, p, j-1)
            return False

        return helper(s, len(s)-1, p, len(p)-1)
    
s = 'abc'
p = 'a*abc'
ss = Solution()
print(ss.isMatch(s, p))

True

Approach 2

Dynamic programming.

The DP optimization feels a lot like edit distance. Beyond mastering recursion, a key skill for learning DP is being able to draw the table.

Draw a table to see the state:

            c   *   a   *   b
        0   1   2   3   4   5
    0   1   0   1   0   1   0
a   1   0   0   0   1   1   0
a   2   0   0   0   0   1   0
b   3   0   0   0   0   0   1

A few subtle / error-prone points — the table uses 1-based strings. The initial setup:

• Initialization, empty-vs-empty match: dp[0][0] = 1
• First row: "c" can match the empty string, "ca*" can match the empty string; p[j-1] != s[i] matches the empty string.
• Moving to the next rows: without a '' the matching is straightforward, but when we hit a '':
• a 1 can propagate from the left: dp[i][j] = dp[i][j-1], i.e. match exactly one occurrence;
• a 1 can propagate from above, when p[j-1] = s[i]: match multiple occurrences, dp[i][j] = dp[i-1][j];
• a 1 can also propagate from two cells to the left: match zero occurrences, just like matching the empty string, dp[i][j] = dp[i][j-2]. Note there are two flavors of matching zero: when p[j-1] != s[i] we are forced to match zero; even when p[j-1] == s[i] we may still choose to match zero.

More code-like:

• s[i] == p[j] or p[j] == '.': dp[i][j] = dp[i-1][j-1]
• p[j] == '*': split into cases
• p[j-1] != s[i]: dp[i][j] = dp[i][j-2] — the match-zero case
• p[j-1] == s[i] or p[i-1] == '.':
  • dp[i][j] = dp[i-1][j] — match multiple s[i]
  • dp[i][j] = dp[i][j-2] — match zero

AC code. Note that the table above uses 1-based strings for convenience; when writing the actual code remember the string is 0-based (though you can also pad the front to simplify indexing).

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        m, n = len(s), len(p)
        dp = [ [0 for i in range(n+1)] for j in range(m+1)]

        dp[0][0] = 1

        # init the first line
        for i in range(2,n+1):
            if p[i-1] == '*':
                dp[0][i] = dp[0][i-2]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1] == '*':
                    if p[j-2] != s[i-1] and p[j-2] != '.':
                        dp[i][j] = dp[i][j-2]
                    elif p[j-2] == s[i-1] or p[j-2] == '.':
                        dp[i][j] = dp[i-1][j] or dp[i][j-2]

                elif s[i-1] == p[j-1] or p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]

        return dp[m][n] == 1 
    
s = 'abc'
p = 'a*abc'
ss = Solution()
print(ss.isMatch(s, p))

True

My dynamic-programming solution follows roughly the same idea as above.

Straight to the state-transition equations. Define some variables first: the string being matched is s, the pattern is p. The DP array dp[i][j] holds whether the first j characters of p match the first i characters of s (true on success, false on failure).

• s[i] == p[j] || p[j] == '.': dp[i][j] = dp[i-1][j-1]. Since the i-th character of s matches the j-th character of p, the first i characters of s match the first j characters of p exactly when the first i-1 characters of s match the first j-1 characters of p.
• p[j] == '*': case split.
• s[i] != p[j-1] && p[j-1] != '.': dp[i][j] = dp[i][j-2] — the character before the '*' is used zero times in the match.
• else: dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2] — either use the '' to match ( dp[i-1][j] ), or match only the character before the '' without using the '' ( dp[i][j-1] ), or use the character before the '' zero times ( dp[i][j-2] ). If any of these is true, the match succeeds.

Finally, the boundary conditions. Initially i runs from 1 to len(s) and j from 1 to len(p). Clearly dp[0][0] is true and everything else false — but that boundary condition is not sufficient. For example, in isMatch("aab", "cab"), dp[1][3] must be derived from dp[0][2], so we need more boundary handling: a leading '*'-pair can match the empty string. Therefore I start i from 0 and also add the i=0 case to the second rule, dp[i][j] = dp[i][j-2].

class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        dp = []
        dp = [[False for i in range(len(p)+1)] for j in range(len(s)+1)]
        dp[0][0] = True
#         print(dp)
        for i in range(len(s)+1):
            for j in range(1, len(p)+1):
                if i > 0 and (s[i-1] == p[j-1] or p[j-1] == '.'):
#                     print("1111111",i)
#                     print("2222222",j)
                    dp[i][j] = dp[i-1][j-1]
#                     print("3333333",dp[i-1][j-1])
                if p[j-1] == '*':
                    if i == 0 or (s[i-1] != p[j-2] and p[j-2] != '.'):
#                         print("4444444",i)
#                         print("5555555",j)
                        dp[i][j] = dp[i][j-2]
#                         print("6666666",dp[i][j-2])
                    else:
                        dp[i][j] = dp[i-1][j] or dp[i][j-1] or dp[i][j-2]
#                         print("7777777",i)
#                         print("8888888",j)
#         print(dp)                       
        return dp[len(s)][len(p)]
    
s = 'aa'
p = 'a*'
ss = Solution()
print(ss.isMatch(s, p))

True

07LeetCode 13: Roman To Integer

Source notebook: 013._Roman_to_Integer.ipynb

013. Roman to Integer

Difficulty: Easy

Problem

Original links

• English: https://leetcode.com/problems/roman-to-integer/
• Chinese: https://leetcode-cn.com/problems/roman-to-integer/description/

Description

Roman numerals are represented by seven symbols: I, V, X, L, C, D and M.

Symbol        Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numerals — two ones side by side. 12 is written as XII, i.e. X + II. 27 is written as XXVII, i.e. XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, there are exceptions: 4 is not IIII but IV — a 1 before a 5, meaning 5 minus 1, i.e. 4. Likewise 9 is written IX. This subtraction rule applies in exactly six cases:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a Roman numeral, convert it to an integer. The input is guaranteed to be in the range 1 to 3999.

Example 1:
Input:  "III"
Output: 3

Example 2:
Input:  "IV"
Output: 4

Example 3:
Input:  "IX"
Output: 9

Example 4:
Input:  "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.

Example 5:
Input:  "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.

Solutions

Approach 1

• Scan from left to right, tracking the current value in a temporary variable.
• If none of the special (subtractive) cases occurs, we simply keep adding digit values one by one and get the correct result.
• A special case occurs when a digit is larger than the one before it — normally each digit is no larger than its predecessor. Then the pair's value is the larger minus the smaller; but note that we already added the previous digit once, so at this point we must subtract it twice.
• Nothing else is tricky. The AC code follows.

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        lookup = {
            'M': 1000,
            'D': 500,
            'C': 100,
            'L': 50,
            'X': 10,
            'V': 5,
            'I': 1
        }
        res = 0
        for i in range(len(s)):
            if i > 0 and lookup[s[i]] > lookup[s[i-1]]:
                res = res + lookup[s[i]] - 2 * lookup[s[i-1]]
            else:
                res += lookup[s[i]]
        return res
    
s = Solution()
string = "MCMXCIV"
print(s.romanToInt(string))

1994

A possible refinement: extract the dictionary lookup into its own function, which reads more elegantly.

def getNum(x):
    return {"I":1,
       "V":5,
       "X":10,
       "L":50,
       "C":100,
       "D":500,
       "M":1000}.get(x)

class Solution:   
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        Num = {
            'M': 1000,
            'D': 500,
            'C': 100,
            'L': 50,
            'X': 10,
            'V': 5,
            'I': 1
        }
        result = 0
        for i in range(len(s)):
            if i > 0 and Num[s[i]] > Num[s[i-1]]:
                result = result + Num[s[i]] - 2 * Num[s[i-1]]
            else:
                result += Num[s[i]]
        return result
    
s = Solution()
string = "MCMXCIV"
print(s.romanToInt(string))

1994

08LeetCode 20: Valid Parentheses

Source notebook: 020._valid_parentheses.ipynb

20. Valid Parentheses

Difficulty: Easy

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/valid-parentheses/description
• English: https://leetcode.com/problems/valid-parentheses

Description

Given a string containing only the characters '(', ')', '{', '}', '[' and ']', determine whether the string is valid.

A string is valid if:

1. Every opening bracket is closed by the same type of bracket.
2. Opening brackets are closed in the correct order.

Note that the empty string is considered valid.

Example 1:
Input:  "()"
Output: true

Example 2:
Input:  "()[]{}"
Output: true

Example 3:
Input:  "(]"
Output: false

Example 4:
Input:  "([)]"
Output: false

Example 5:
Input:  "{[]}"
Output: true

Solutions

Approach 1

We only need to match three pairs: "(" -> ")", "[" -> "]", "{" -> "}".

The essential idea here is the stack: push every opening bracket, pop on every closing bracket, and check the correspondence.

Things to verify:

• When a closing bracket appears, is there anything left on the stack at all?
• When popping, do the brackets actually correspond?
• Is the stack empty at the end?

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        LEFT = {'(', '[', '{'}  # opening brackets
        RIGHT = {')', ']', '}'}  # closing brackets
        stack = []  # create a stack
        for brackets in s:  # iterate over the whole input string
            if brackets in LEFT:  # if the current character is an opening bracket
                stack.append(brackets)  # push the opening bracket
            elif brackets in RIGHT:  # if it is a closing bracket
                if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2:
                    # stack is empty, e.g. ()]
                    # or closing minus opening char code is not between 1 and 2 (no pairing)
                    return False  # return False
                stack.pop()  # pop the opening bracket
        return not stack  # True if the stack is empty, otherwise False
    
s = Solution()
print(s.isValid("([[])[]{}"))
print(s.isValid("([])[]{}"))

False
True

Same as Approach 1, but an easier-to-follow version:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        leftP = '([{'
        rightP = ')]}'
        stack = []
        for char in s:
            if char in leftP:
                stack.append(char)
            if char in rightP:
                if not stack:
                    return False
                tmp = stack.pop()
                if char == ')' and tmp != '(':
                    return False
                if char == ']' and tmp != '[':
                    return False       
                if char == '}' and tmp != '{':
                    return False
        return stack == []
    
s = Solution()
print(s.isValid("([[])[]{}"))
print(s.isValid("([])[]{}"))

False
True

Approach 2

• More extensible and easier to reason about.
• Uses a dictionary to store the bracket pairings.

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s) % 2 == 1:
            return False

        index = 0
        stack = [i for i in s]
        map1 = {"(": ")", "[": "]", "{": "}"}

        while len(stack) > 0:
            # check whether the index runs past the boundary
            if index >= len(stack)-1:
                return False
    
            b = stack[index]
            e = stack[index+1]

            if b not in map1.keys():
                return False
            elif e in map1.keys():
                index += 1
            elif map1[b] == e:
                stack.pop(index+1)
                stack.pop(index)
                index = 0 if index-1<0 else index-1
            else:
                return False

        return stack == []
    
s = Solution()
print(s.isValid("([[])[]{}"))
print(s.isValid("([])[]{}"))

False
True

Approach 3

• Bracket matching done a different way.
• First push everything onto a list used as a stack (regardless of whether the first symbol is an opening bracket), then walk it element by element, popping whenever a matching pair lines up; at the end simply check whether the stack is empty.

l_d = {
    '{': -3,
    '(': -2,
    '[': -1,
    ']': 1,
    ')': 2,
    '}': 3,
}
    
class Solution:
    def isValid(self, s):
        l_s = []
        for c_r in s:
            if len(l_s) == 0:
                l_s.append(c_r)
                continue

            c_l = l_s[-1]

            if l_d[c_l] + l_d[c_r] == 0 and l_d[c_l] < 0:
                l_s.pop()
            else:
                l_s.append(c_r)

        if len(l_s) == 0:
            return True
        else:
            return False
        
s = Solution()
print(s.isValid("([[])[]{}"))
print(s.isValid("([])[]{}"))

False
True

09LeetCode 32: Longest Valid Parentheses

Source notebook: 032._longest_valid_parentheses.ipynb

032. Longest Valid Parentheses

Difficulty: Easy

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/longest-valid-parentheses/description
• English: https://leetcode.com/problems/longest-valid-parentheses

Description

Given a string containing only '(' and ')', find the length of the longest substring of valid (well-formed) parentheses.

Example 1:
Input:  "(()"
Output: 2
Explanation: the longest valid substring is "()"

Example 2:
Input:  ")()())"
Output: 4
Explanation: the longest valid substring is "()()"

Solutions

Approach 1

Note: careful — this problem has a trap right out of the gate. The statement glosses over a case such as "(())", where the valid-parentheses substring has length 4, not an error.

Seeing this longest-valid-parentheses problem immediately reminded me of an earlier one — LeetCode 20 — whose solution uses a stack to decide whether a bracket sequence pairs up successfully. We can carry the stack idea over here.

Whenever we meet an opening bracket, or a closing bracket that cannot be paired, we push its index onto the stack; brackets that do pair up are popped. What remains on the stack are the indices of unpaired brackets. We can then measure the gaps between those indices to obtain the maximum paired-parentheses length. Here we first traverse the string once, then traverse the non-empty stack. Keep firmly in mind that the non-empty stack holds the indices of the brackets that failed to match — every matched bracket has already been popped.

class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        # create a list used as a stack
        stack = []
        # first pass over the string s
        for i in range(len(s)):
            # if the current character is a closing bracket, check the stack for a matching opening bracket
            if s[i] == ')':
                # if the stack is non-empty and its top index points at an opening bracket in s
                if stack and s[stack[-1]] == '(':
                    # pop the top element and pair it with the current closing bracket
                    stack.pop()
                    # simply continue
                    continue
            stack.append(i)
        # maximum length so far
        max_length = 0
        # initialized to the length of s
        next_index = len(s)
        # traverse the non-empty stack
        while stack:
            # index into s stored at the top of the stack
            cur_index = stack.pop()
            # compute the next candidate valid-parentheses length
            cur_length = next_index - cur_index - 1
            # compare with the stored max_length and keep the larger
            max_length = max(cur_length, max_length)
            # set the right boundary for the next segment and loop until the stack is empty
            next_index = cur_index
        # at the end, next_index is the length of the leading valid segment; return the larger of it and max_length
        return max(next_index, max_length)
            
    
s = Solution()
print(s.longestValidParentheses("()(())"))
print(s.longestValidParentheses("()()(()"))

6
4

Approach 2

Solve it with dynamic programming.

This one was devised by Pianke — the idea is genuinely elegant. Reference: http://www.cnblogs.com/George1994/p/7531574.html

1. Use a dp array where dp[i] holds the length of the longest valid parentheses substring ending at index i. For example, dp[3] = 2 means the longest valid substring ending at index 3 has length 2.
2. Clearly dp[i] and dp[i-1] are related: - When the character at index i is "(" — i.e. s[i] == '(' — obviously dp[i] contributes nothing new: dp[i] = dp[i-1] + 0, i.e. nothing to do. - When the character at index i is ")" — i.e. s[i] == ')' — if there is a '(' just before the longest valid substring represented by dp[i-1] that pairs with s[i], then dp[i] = dp[i-1] + 2, and we can keep extending further back (if the earlier part chains on as well).

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        dp = [0 for i in range(len(s))]
        for i in range(1, len(s)):
            if s[i] == ')':
                left = i - 1 - dp[i-1]
                if left >= 0 and s[left] == '(':
                    dp[i] = dp[i-1] + 2
                    if left > 0: # check whether the part before `left` chains onto this match
                        dp[i] += dp[left-1]
        return max(dp)

s = Solution()
print(s.longestValidParentheses("()(())"))
print(s.longestValidParentheses("()()(()"))

6
4

10LeetCode 53: Maximum Subarray

Source notebook: 053._maximum_subarray.ipynb

53. Maximum Subarray

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/maximum-subarray/description/
• English: https://leetcode.com/problems/maximum-subarray/

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

Example:

Input:  [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: the contiguous subarray [4,-1,2,1] has the largest sum, 6.

Follow-up:
If you have an O(n) solution, try the subtler divide-and-conquer approach.

Solutions

Approach 1

• An O(N^2) double loop works conceptually.
• Starting from i, compute sums out to n and keep the larger sum.
• It times out, though — will not be accepted (no AC).

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # initialize to negative infinity
        ans = float('-inf')
        # this loop controls the length of the subarray
        for i in range(1, len(nums)):
            # this loop controls the starting position of the subarray
            for j in range(len(nums)-i):
                big = 0
                big = sum(nums[j : j+i])
                if big > ans:
                    ans = big
        return ans

s = Solution()
nums_1 = [-2,1,-3,4,-1,2,1,-5,4]
nums_2 = [1, -1]
print(s.maxSubArray(nums_1))
print(s.maxSubArray(nums_2))

6
1

Approach 2

• Use dynamic programming.
• ms(i) = max(ms[i-1] + a[i], a[i])
• All we need to know: the maximum ending at i comes from one of two options — extend with a[i], or restart the subarray at a[i].
• Compare ms[i-1] + a[i] against a[i]. If the former is smaller, the best sum of the preceding subarray is negative, so we can discard it and restart the subarray at a[i]; if the former is larger, the preceding subarray's best sum is positive and we extend it with a[i].
• This one is accepted (AC).

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        maxSum = [nums[0] for i in range(n)]
        for i in range(1,n):
        	maxSum[i] = max(maxSum[i-1] + nums[i], nums[i])
        return max(maxSum)
    
s = Solution()
nums_1 = [-2,1,-3,4,-1,2,1,-5,4]
nums_2 = [1, -1]
print(s.maxSubArray(nums_1))
print(s.maxSubArray(nums_2))

6
1

Approach 3

Kadane's Algorithm — see Wikipedia. The common variant resets negative sums to 0; here it needs a small modification. Reference: http://algorithms.tutorialhorizon.com/kadanes-algorithm-maximum-subarray-problem/

start:
    max_so_far = a[0]
    max_ending_here = a[0]

loop i= 1 to n
  (i) max_end_here = Max(arrA[i], max_end_here+a[i]);
  (ii) max_so_far = Max(max_so_far,max_end_here);

return max_so_far

The AC code follows:

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        maxSum , maxEnd = nums[0], nums[0]
        
        for i in range(1,n):
            maxEnd = max(nums[i],maxEnd + nums[i])
            maxSum = max(maxEnd,maxSum)
        return maxSum
    
s = Solution()
nums_1 = [-2,1,-3,4,-1,2,1,-5,4]
nums_2 = [1, -1]
print(s.maxSubArray(nums_1))
print(s.maxSubArray(nums_2))

6
1

Approach 4

See CLRS p. 71 — divide and conquer, with pseudocode there.

The maximum subarray sum has three possible locations: the left half, the right half, or straddling the midpoint.

Slower, but accepted; complexity O(NlogN).

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def find_max_crossing_subarray(nums, low, mid, high):
            left_sum = float('-inf')
            sum = 0
            for i in xrange(mid,low-1,-1):
                sum = sum + nums[i]
                if sum > left_sum:
                    left_sum = sum

            right_sum = float('-inf')
            sum = 0
            for j in range(mid+1,high+1):
                sum = sum + nums[j]
                if sum > right_sum:
                    right_sum = sum

            return left_sum + right_sum

        def find_max_subarray(nums,low,high):
            if low == high: 
                return nums[low]
            else:
                mid = (low + high) / 2
                left_sum = find_max_subarray(nums, low, mid)
                right_sum = find_max_subarray(nums,mid+1,high)
                cross_sum = find_max_crossing_subarray(nums,low,mid,high)
                # print left_sum, right_sum, cross_sum
                # print mid, low, high
                return max(left_sum, right_sum, cross_sum)

        return find_max_subarray(nums, 0, len(nums)-1)

11LeetCode 62: Unique Paths

Source notebook: 062._unique_paths.ipynb

062. Unique Paths

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/unique-paths/description
• English: https://leetcode.com/problems/unique-paths

Description

A robot is located at the top-left corner of an m x n grid (marked "Start" in the diagram below).

The robot can only move either down or right at any point in time. It is trying to reach the bottom-right corner of the grid (marked "Finish").

How many unique paths are there?

Note: m and n are at most 100.

Example 1:
Input:  m = 3, n = 2
Output: 3
Explanation:
Starting from the top-left corner there are 3 paths to the bottom-right corner.
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:
Input:  m = 7, n = 3
Output: 28

For example, the picture below shows a 3 x 7 grid. How many possible paths are there?

Solutions

Approach 1

The mathematical route.

At heart this is combinatorics: the walk takes m + n - 2 steps in total, of which m - 1 go one direction — so it is simply choosing m - 1 out of m + n - 2, a factorial problem. Easy! This method beats 99.97%.

Bonus: the math module ships a factorial function; just import math and call it.

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        def factorial(num):
            res = 1
            for i in range(1, num+1):
                res *= i
            return res
        return factorial(m+n-2)/factorial(n-1)/factorial(m-1)
    
s = Solution()
print(s.uniquePaths(7,3))

28.0

Approach 2

Pianke came up with this one — a great idea!

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m < 1 or n < 1:
            return 0
        dp = [0] *n
        dp[0] = 1    
        for i in range(0,m):
            for j in range(1,n):
                dp[j] += dp[j-1]
        return dp[n-1]
    
s = Solution()
print(s.uniquePaths(7,3))

28

12LeetCode 64: Minimum Path Sum

Source notebook: 064._minimum_path_sum.ipynb

064. Minimum Path Sum

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/minimum-path-sum/description
• English: https://leetcode.com/problems/minimum-path-sum

Description

Given an m x n grid filled with non-negative numbers, find a path from the top-left corner to the bottom-right corner that minimizes the sum of the numbers along the path.

Note: you can only move down or right at each step.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: the path 1→3→1→1→1 has the minimal sum.

Solutions

Approach 1

Use dynamic programming. Observe that a cell at position [i][j] can be reached by exactly 2 routes: from above ([i-1][j] -> [i][j]) or from the left ([i][j-1] -> [i][j]). We only need to take whichever of the two has the smaller path sum. See also problem 072, Edit Distance.

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        m = len(grid)
        n = len(grid[0])
        dp = grid.copy()
        for i in range(1, n):
            dp[0][i] = dp[0][i-1] + grid[0][i]
        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i][j-1] + grid[i][j], dp[i-1][j] + grid[i][j])
        return dp[m-1][n-1]
    
s = Solution()
grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
print(s.minPathSum(grid))

7

The version above is my first draft. Following advice to keep the number of for loops down, I rewrote it into the final version below, which is accepted (AC).

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid or len(grid) == 0:
            return 0
        row = len(grid)
        col = len(grid[0]) if row else 0
        dp = [[0 for j in range(col)] for i in range(row)]
        for i in range(row):
            for j in range(col):
                if i > 0 and j > 0:
                    dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])
                elif i > 0 and j == 0:
                    dp[i][j] = sum([grid[k][0] for k in range(i+1)])
                elif i == 0 and j > 0:
                    dp[i][j] = sum([grid[0][k] for k in range(j+1)])
                else:
                    dp[i][j] = grid[0][0]
        return dp[-1][-1]
    
s = Solution()
grid = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
print(s.minPathSum(grid))

7

13LeetCode 72: Edit Distance

Source notebook: 072._edit_distance.ipynb

072. Edit Distance

Difficulty: Hard

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/edit-distance/description/
• English: https://leetcode.com/problems/edit-distance/

Description

Given two words word1 and word2, find the minimum number of operations required to convert word1 into word2.

You may perform the following three operations on a word:

Insert a character
Delete a character
Replace a character

Example 1:
Input:  word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose  (delete 'r')
rose  -> ros   (delete 'e')

Example 2:
Input:  word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (delete 't')
inention -> enention  (replace 'i' with 'e')
enention -> exention  (replace 'n' with 'x')
exention -> exection  (replace 'n' with 'c')
exection -> execution (insert 'u')

Solutions

This problem is the canonical dynamic-programming example; Wikipedia has dedicated pages for it:

• https://en.wikipedia.org/wiki/Edit_distance#Common_algorithm
• https://en.wikipedia.org/wiki/Levenshtein_distance

Approach 1

• Use dynamic programming.

Here is the idea in detail.

Always keep in mind what dp[i][j] means: the number of operations required to make the first i characters of word1 equal to the first j characters of word2. That is also why the dp matrix is initialized with one extra row and column.

We create a 2-D array dp[][] representing the minimum number of steps needed to edit the first i characters of word1 (indices 0 ~ i-1) into the first j characters of word2 (indices 0 ~ j-1). Then:

If $word1[i] = word2[j]$ then $dp[i][j] = dp[i-1][j-1]$

If $word1[i] != word2[j]$ then $dp[i][j] = min ( dp[i-1][j] , dp[i][j-1], dp[i-1][j-1] ) + 1$

Here is the explanation of that recurrence:

The first case is easy: if character i of word1 equals character j of word2, no operation is needed at this position, so we only care about the result for the substrings with those characters removed.

Let's focus on the three options in the second case:

Suppose the first i+1 characters (indices 0~i) of word1 are "abcde", and the first j+1 characters (indices 0~j) of word2 are "abcddgf". Now word1[i] != word2[j], i.e. 'e' != 'f'.

What should we do next?

Notice that the three interpretations below are exactly the three allowed operations, simulated as the final step. Each adds one extra operation.

Simply put: - 1. delete: dp[i-1][j] + 1 — keeps the optimal count for transforming word1[0~i-1] into word2[0~j]. Since word1's first 0~i-1 characters can already be transformed into word2, we just delete word1's final character — one extra delete operation. - 2. insert: dp[i][j-1] + 1 — keeps the optimal count for transforming word1[0~i] into word2[0~j-1]. Since word1[0~i] only reaches word2's second-to-last position, we append to word1 a character equal to word2's last character — one extra insert operation. - 3. replace: dp[i-1][j-1] + 1 — keeps the optimal count for transforming word1[0~i-1] into word2[0~j-1]. Since word1[0~i-1] reaches word2's second-to-last position and the last characters differ, a single replace of the final character suffices — one extra replace operation.

Whichever of the three we pick, we take the minimum of their values.

Reference: http://www.cnblogs.com/pandora/archive/2009/12/20/levenshtein_distance.html

Now the code:

class Solution:
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        # initialize a (len(word1)+1) x (len(word2)+1) matrix
        matrix = [[i+j for j in range(len(word2) + 1)] for i in range(len(word1) + 1)]
        # to aid understanding, this is what the matrix looks like
        # print(matrix)
        for i in range(1, len(word1)+1):
            for j in range(1,len(word2)+1):
                if word1[i-1] == word2[j-1]:
                    d = 0
                else:
                    d = 1
                matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d)

        return matrix[len(word1)][len(word2)]
    
s = Solution()
word1 = 'horse'
word2 = 'ros'
print(s.minDistance(word1, word2))

3

The way the matrix is generated in the code above can be confusing — I only understood the details after asking around.

Let's print it out.

import numpy as np
juzhen = [[i+j for j in range(len(word2) + 1)] for i in range(len(word1) + 1)]
juzhen = np.mat(juzhen)
juzhen

matrix([[0, 1, 2, 3],
        [1, 2, 3, 4],
        [2, 3, 4, 5],
        [3, 4, 5, 6],
        [4, 5, 6, 7],
        [5, 6, 7, 8]])

Printed numpy-style it is much clearer — rows and columns line up neatly.

What I want to point out:

• Row 1 of the matrix (the row with index 0), [0, 1, 2, 3], corresponds to dp[i][j] — the minimum number of edits to turn the first i characters of word1 into word2. Here i = 0, so word1 contributes 0 characters, while j ranges over 0–3 characters of word2. Essentially we start from an empty word1 and insert word2's characters one by one; the minimum number of edits equals however many characters of word2 we take — exactly the numbers along this dimension.

• Along the other dimension, column 1 of the matrix (the column with index 0), [0, 1, 2, 3, 4, 5], also corresponds to dp[i][j], with the roles swapped: now j = 0 and i varies. It is the minimum number of steps to transform the first 0~i characters of word1 into word2 when word2 is empty — i.e. we delete however many characters word1 has. Those are the numbers along the column dimension.

• Everywhere else — where neither i nor j is 0 — the initialization values are meaningless; the iteration overwrites all of them.

14LeetCode 139: Word Break

Source notebook: 139._word_break.ipynb

Word Break

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/word-break/description/
• English: https://leetcode.com/problems/word-break/

Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine whether s can be segmented into a space-separated sequence of one or more dictionary words.

Notes:

1. The same dictionary word may be reused multiple times in the segmentation.
2. You may assume the dictionary contains no duplicate words.

Example 1:
Input:  s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: return true because "leetcode" can be segmented as "leet code".

Example 2:
Input:  s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: return true because "applepenapple" can be segmented as "apple pen apple".
     Note that dictionary words may be reused.

Example 3:
Input:  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Solutions

Approach 1

• Take a string S of length N. If S can be assembled by concatenating words from the dictionary (dict), the condition to satisfy is:
  • F(0, N) = F(0, i) && F(i, j) && F(j, N)
  • Thus, to know whether some substring can be pieced together from dictionary words, we compute it this way (True if satisfied, False otherwise) and store the result at the corresponding position of a boolean array. The last element of the boolean array is then the value of F(0, N): True means the string S can be assembled from dictionary words, otherwise it cannot.
• AC code below.

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        # validate the arguments
        if s is None or len(s) < 1 or wordDict is None or len(wordDict) < 1:
            return False
        # match flags: match[i] means s[0..i-1] can be segmented
        length = len(s)
        match = [False for i in range(length + 1)]
        match[0] = True
        
        for i in range(1, length +1):
            for j in range(i):
                if match[j] and s[j:i] in wordDict:
                    match[i] = True
                    break
        return match[length]


sss = Solution()
s = "leetcode"
wordDict = ["leet", "code"]
print(sss.wordBreak(s, wordDict))

True

Approach 2

• ok[i] indicates whether s[:i] can be built from our dictionary.
• The principle is similar to Approach 1 above.

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        ok = [True]
        for i in range(1, len(s)+1):
            ok += [any(ok[j] and s[j:i] in wordDict for j in range(i))]
        return ok[-1]
    
sss = Solution()
s = "leetcode"
wordDict = ["leet", "code"]
print(sss.wordBreak(s, wordDict))

True

Different ways of appending to a list vary in speed. A comparison:

>>> from timeit import timeit
>>> timeit('x.append(1)', 'x = []', number=10000000)
1.9880003412529277
>>> timeit('x += 1,',     'x = []', number=10000000)
1.2676891852971721
>>> timeit('x += [1]',    'x = []', number=10000000)
3.361207239950204

So we might be tempted to rewrite the code as:

ok += any(ok[j] and s[j:i] in wordDict for j in range(i))  # raises an error

But this raises TypeError: 'bool' object is not iterable — a bool cannot be added to a list this way, though other types can (with lists themselves, mind the semantics).

So in this case we do it like this:

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        ok = [True]
        for i in range(1, len(s)+1):
            ok += any(ok[j] and s[j:i] in wordDict for j in range(i)),
        return ok[-1]
    
sss = Solution()
s = "leetcode"
wordDict = ["leet", "code"]
print(sss.wordBreak(s, wordDict))

True

15LeetCode 179: Largest Number

Source notebook: 179._Largest_Number.ipynb

179. Largest Number

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/largest-number/description/
• English: https://leetcode.com/problems/largest-number/

Description

Given a list of non-negative integers, arrange them so that they form the largest possible number.

Example 1:
Input:  [10,2]
Output: 210

Example 2:
Input:  [3,30,34,5,9]
Output: 9534330
Note: the result may be very large, so return a string instead of an integer.

Solutions

Approach 1

• Sort first, then join; if the result is an empty string, return '0'.

The sorting relies on the classic string comparison:

Note: Python 3 dropped cmp and only takes key; use functools.cmp_to_key to wrap a comparator.

A cmp function compares two objects (x, y): it returns 1 if x > y, 0 if x == y, and -1 if x < y.

The following is the Python 2 solution — it gets accepted (AC), but under Python 3 it raises the error shown below.

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        nums = [str(num) for num in nums]
        nums.sort(cmp=lambda x, y: cmp(y+x, x+y))
        return ''.join(num).lstrip('0') if ''.join(num).lstrip('0') else '0'
    
s = Solution()
nums = [10, 2]
print(s.largestNumber(nums))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-1-ac3558977848> in <module>()
     11 s = Solution()
     12 nums = [10, 2]
---> 13 print(s.largestNumber(nums))

<ipython-input-1-ac3558977848> in largestNumber(self, nums)
      6         """
      7         nums = [str(num) for num in nums]
----> 8         nums.sort(cmp=lambda x, y: cmp(y+x, x+y))
      9         return ''.join(num).lstrip('0') if ''.join(num).lstrip('0') else '0'
     10 

TypeError: 'cmp' is an invalid keyword argument for this function

Or, even simpler, it can be written like this (works in Python 2; raises an error in Python 3):

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        nums = [str(num) for num in nums]
        nums.sort(cmp=lambda x, y: cmp(y+x, x+y))
        return ''.join(num).lstrip('0') or '0'
    
s = Solution()
nums = [10, 2]
print(s.largestNumber(nums))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-2-af910a43d954> in <module>()
     11 s = Solution()
     12 nums = [10, 2]
---> 13 print(s.largestNumber(nums))

<ipython-input-2-af910a43d954> in largestNumber(self, nums)
      6         """
      7         nums = [str(num) for num in nums]
----> 8         nums.sort(cmp=lambda x, y: cmp(y+x, x+y))
      9         return ''.join(num).lstrip('0') or '0'
     10 

TypeError: 'cmp' is an invalid keyword argument for this function

The solution below is the Python 3 version.

from functools import cmp_to_key

# comparator function
def compare(a, b):
    return int(b + a) - int(a + b)

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        nums = sorted([str(x) for x in nums], key=cmp_to_key(compare))
        return str(int(''.join(nums)))
    
s = Solution()
nums = [10, 2]
print(s.largestNumber(nums))

210

16LeetCode 242: Valid Anagram

Source notebook: 242._valid_anagram.ipynb

242. Valid Anagram

Difficulty: Easy

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/valid-anagram/description/
• English: https://leetcode.com/problems/valid-anagram/

Description

Given two strings s and t, write a function to determine whether t is an anagram of s.

Example 1:
Input:  s = "anagram", t = "nagaram"
Output: true

Example 2:
Input:  s = "rat", t = "car"
Output: false

Note:
You may assume the strings contain only lowercase letters.

Follow-up:
What if the inputs contain unicode characters? How would you adapt your solution?

Solutions

Approach 1

• A one-liner!
• Uses the collections.Counter() method.

import collections

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return collections.Counter(s) == collections.Counter(t)
    
s = "anagram"
t = "nagaram"
ss = Solution()
print(ss.isAnagram(s, t))

True

Approach 2

• Also a one-liner!
• Uses the sorted() function.

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        return sorted(s) == sorted(t)
s = "anagram"
t = "nagaram"
ss = Solution()
print(ss.isAnagram(s, t))

True

Approach 3

• Count character frequencies — there are only 26 possible letters.

class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        
        charCnt = [0] * 26
        
        for i in range(len(s)):
            charCnt[ord(s[i]) - 97] += 1
            charCnt[ord(t[i]) - 97] -= 1 
        
        for cnt in charCnt:
            if cnt != 0:
                return False
        return True
    
s = "anagram"
t = "nagaram"
ss = Solution()
print(ss.isAnagram(s, t))

True

17LeetCode 287: Find The Duplicate Number

Source notebook: 287._Find_the_Duplicate_Number.ipynb

287. Find the Duplicate Number

Difficulty: Medium

Problem

Original links

• Chinese: https://leetcode-cn.com/problems/find-the-duplicate-number/description/
• English: https://leetcode.com/problems/find-the-duplicate-number

Description

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), at least one duplicate number must exist. Assuming there is exactly one duplicated number, find it.

Example 1:
Input:  [1,3,4,2,2]
Output: 2

Example 2:
Input:  [3,1,3,4,2]
Output: 3

Notes:
You must not modify the array (it is read-only).
You may only use O(1) extra space.
The runtime complexity must be less than O(n2).
There is only one duplicated number, but it may appear more than once.

Solutions

Approach 1

On first reading, the problem doesn't feel very hard. But once we reach the notes — the constraints on the problem — its difficulty suddenly jumps several times over.

The points to watch: - The array contains n+1 integers. - The numbers lie between 1 and n inclusive (but need not be contiguous, e.g. [1,4,4,3,4]). - The duplicated number may repeat many times — not just once, twice, or three times. - The array must not be modified (the killer constraint: my original plan was to sort and then binary-search, which this rule forbids). - Only O(1) extra space is allowed. (O(1) space means the extra memory does not grow with the array length: no matter how long the array, we may use only a fixed amount m that does not change with n.) - Time complexity must be below $O(n^2)$.

Those are essentially all the constraints.

This approach uses binary search + the Pigeonhole Principle.
Wikipedia entry on the pigeonhole principle: https://en.wikipedia.org/wiki/Pigeonhole_principle

The two constraints "no modifying the array" and "constant space" imply: no sorting, and no Map-like data structures.

A runtime below O(n^2) suggests using binary search to reduce one of the n factors to log n.
See LeetCode Discuss: https://leetcode.com/discuss/60830/python-solution-explanation-without-changing-input-array

Binary-search over the answer range, validating each guess with the pigeonhole principle.

By the pigeonhole principle, among n+1 integers in the range [1, n] some number must appear at least twice.
Suppose the candidate is n / 2:
scan the array; if more than n / 2 elements are <= n / 2, a solution must lie within [1, n/2]; otherwise the solution lies in (n/2, n].

Another way to see it:

If n is 5, the possible values are 1 2 3 4 5 — five numbers — while the array size is 6, so some number must appear at least twice.

With no duplicates, the count of numbers <= 1 equals 1;

the count of numbers <= 2 equals 2;

... and likewise for 3, 4, 5.

With a duplicate — say 1 is duplicated — the count of numbers <= 1 is certainly greater than 1.

Based on this, pick a mid among 1 2 3 4 5 and scan the array counting elements <= mid. Is the count <= mid, or > mid?

If the count is <= mid, the numbers 1..mid contain no duplicate, and the duplicate lies in the right half (mid..n) — narrow the search to the right half.

If the count is > mid, the numbers 1..mid contain the duplicate — narrow the search to the left half.

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low, high = 1, len(nums) - 1
        while low <= high:
            mid = (low + high) >> 1
            cnt = sum(x <= mid for x in nums)
            if cnt > mid:
                high = mid - 1
            else:
                low = mid + 1
        return low
    
s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3

Approach 1 runs in $O(nlogn)$; Approach 2 below runs in $O(n)$ time, though it bends the rules somewhat.

Approach 2

One pass to count, another pass to report.

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = dict()
        for n in nums:
            dic[n] = dic.get(n, 0) + 1
            if dic[n] >= 2:
                return n

s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3

Approach 3

Approach 3 is the fully compliant $O(n)$ solution (Floyd's cycle detection). I haven't completely internalized it yet, so I'll leave it below for study.

class Solution(object):
    def findDuplicate(self, nums):
        # The "tortoise and hare" step.  We start at the end of the array and try
        # to find an intersection point in the cycle.
        slow = 0
        fast = 0
    
        # Keep advancing 'slow' by one step and 'fast' by two steps until they
        # meet inside the loop.
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
    
            if slow == fast:
                break
    
        # Start up another pointer from the end of the array and march it forward
        # until it hits the pointer inside the array.
        finder = 0
        while True:
            slow   = nums[slow]
            finder = nums[finder]
    
            # If the two hit, the intersection index is the duplicate element.
            if slow == finder:
                return slow
            
s = Solution()
nums = [1,2,3,3]
print(s.findDuplicate(nums))

3