Posts

Showing posts from April, 2022

Minimum Insertion Steps to Make a String Palindrome

Image
A word, phrase, or sequence that reads the same backwards as forwards is a palindrome. For example the sequence "Step on no pets" is a palindrome. Today, let's focus on converting a sequence into a palindrome by inserting characters at arbitrary positions in the original input sequence. Minimum Insertion Steps to Make a String Palindrome - Problem Statement Given an input sequence $s$, in one step you can insert any character at any position of the input sequence. Return the minimum number of steps to make $s$ palindrome. For example, given the input sequence "leetcode", inserting five characters the string becomes "leetcodocteel". This is the minimum number of insertions required to make the input sequence a palindrome. Minimum Insertion Steps to Make a String Palindrome - Definition Let $s$ be an input sequence, $i$ and $j$ denote the start and end positions of a subsequence. Let $p[i][j]$ be the minimum number of insertions required to make subseque

Elementary Graph Algorithms - Breadth First Search

Graph problems pervade computer science, and algorithms to working with them are fundamental to the field. Hundreds of interesting computational problems are couched in terms of graphs. In this part, we touch the Breadth First Search. Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Given a graph $G = (V, E)$ and a distinguished source vertex $s$, breadth-first search systematically explores the edges of $G$ to discover every vertex that is reachable from $s$. It computes the distance (smallest number of edges) from $s$ to each reachable vertex. [1] Now let’s consider a real world application of the BFS algorithm.  Treasure Island - Problem Definition You have a map that marks the location of a treasure island. Some of the map area has jagged rocks and dangerous reefs. Other areas are safe to sail in. There are other explorers trying to find the treasure. So you must figure out a shortest route to the tr