For a given string, to get the minimum substring that contains all the characters we want is not easy to do. When screening through the string, we always use an algorithm called “sliding window” which uses two pointers to locate the substring. In this post, I’ll introduce this algorithm by solving this problem together: minimum window substring.
Given two strings
t, return the minimum window in
swhich will contain all the characters in
t. If there is no such window in
sthat covers all characters in
t, return the empty string
Note that If there is such a window, it is guaranteed that there will always be only one unique minimum window in
It’s a quite common problem in real life: how to find the minimum number of coins, to pay a specific amount with coins of different denominations? When I first see this problem in Leetcode, it took me a while to figure it out. After learning more about dynamic programming, I found it’s easy to understand and solve this problem. In this post, I'll introduce the algorithm and code to solve this classic problem.
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. …
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
The Linked List is represented in the input/output as a list of
nnodes. Each node is represented as a pair of
val: an integer representing
random_index: the index of the node (range from
n-1) where random pointer points to, or
nullif it does not point to any node.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
You can solve this problem here: leetcode 138. …
For the linear data structure, elements are inserted/deleted in a specific order. For example, the queue follows FIFO(first-in-first-out) pattern, whereas the stack follows the FILO(first-in-last-out) pattern. In the real world, only following fixed rules will not solve problems. For instance, jobs sent to a printer are placed in a queue. If we have a really important job that’s needed immediately, we might want the job to be run as soon as the printer is available. This particular scenario needs a special kind of queue, known as a priority queue. …
Intro to a double-ended queue
Speaking of linear data structures, we can think of the list, stack, queue, and linked list. These linear data structures are convenient in adding/removing elements from a collection. However, there’s a common problem: it’s not easy to access elements from the front or end of the collection. In this post, I’ll introduce another linear data structure that solves this problem — deque.
Deque is the abbreviation of the double-ended queue. As it sounds like, it generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). …
When talking about linear data structures, we mostly can think of array and linked list. In fact, another linear data structure called stack is also frequently used in computer science. In this post, I’ll talk about the definition, applications, and implementation of a stack.
A stack is similar to an array, is a collection of elements. Elements in a stack follow two main operations:
All elements in a stack obey such a rule so that create a special order: last in, first out, usually referred to as LIFO. …
The linked list is a linear data structure, constructed by nodes. The linked list performed great in inserting and deleting elements. In a technical interview, linked list problems are frequently asked. In this post, I’ll introduce a classic problem in the linked list structure: reverse a linked list.
If you’re not familiar with the singly-linked list, here’s a brief introduction. A singly-linked list is constructed by nodes. Each node has a value and a pointer points to the next node. We can write a simple class:
def __init__(self, val = 0, next = None):
self.val = val
Two pointers algorithm is frequently used in solving array/list problems. One classic example is the Two Sum problem. In this post, let’s solve some two pointers problems together.
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
Input: numbers = [2,7,11,15], target = 9
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
Try to solve it yourself at https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
As we can see from the input, the array is already sorted in ascending order. In order to find the two numbers
b that add up to the target, we can have two pointers point to them individually. Initially, we can have one pointe points to the first element, and another pointer points to the last element of the input array. …
According to Wikipedia:
A regular expression (shortened as regex or regexp; also referred to as rational expression) is a sequence of characters that define a search pattern. Usually such patterns are used by string-searching algorithms for “find” or “find and replace” operations on strings, or for input validation. It is a technique developed in theoretical computer science and formal language theory.
To me, the regular expression is magical. It has many rules and symbols to represent a long string. In this post, I’ll introduce a simple regular expression matching rule and implementation.
Given an input string (
s) and a pattern (
p), implement regular expression matching with support for
Breadth-first search (BFS) is an algorithm that’s widely applied to data structures such as tree/graph/matrix. The BFS allows us to get the target value by using a queue to store the traveled elements. In this post, I’ll introduce a classical leetcode problem that’s using BFS in the matrix.
m x n2d
'1's (land) and
'0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:Input: grid = [