[Leetcode]1286. Iterator for Combination

Design an Iterator class, which has:
A constructor that takes a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
A function next() that returns the next combination of length combinationLength in lexicographical order.
A function hasNext() that returns True if and only if there exists a next combination.
Constraints:
1 <= combinationLength <= characters.length <= 15
There will be at most 10^4 function calls per test.
It's guaranteed that all calls of the function next are valid.
Continue reading “[Leetcode]1286. Iterator for Combination”

[Leetcode]212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
Input: board =
[ ['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v'] ]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Continue reading “[Leetcode]212. Word Search II”

Depth-First-Search(DFS) vs Dynamic Programming(DP)

DFS is a searching algorithm that would go as far as possible before backtracking, and Dynamic Programming, referring to GeeksforGeeks, is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. What are connections do they share? Let me uncover this by a Leetcode problem: 494. Target Sum.

Continue reading “Depth-First-Search(DFS) vs Dynamic Programming(DP)”

Intro to Graph Algorithms – BFS & DFS

Graphs are a pervasive data structure in computer science, and algorithms for working with them are fundamental to the field.

Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2009.

Given a graph defined as G=(V,E) which is a set of vertices and edges, we’d be curious about how to represent it and how to search it systematically so as to visit the vertices following the edges. This blog will briefly introduce two ways of representations of a graph, and then will dive deep into two graph search algorithms: Breadth-First-Search (BFS) and Depth-First-Search (DFS).

Continue reading “Intro to Graph Algorithms – BFS & DFS”