Close

Edit distance 1

Given two strings, how do we check if their edit distance is 1? Edit distance is defined as the number of characters that needs to be modified, inserted or deleted from one string to transform into the other string. For example let us consider two strings “java”, “lava” they both differ by just one character.…

Longest common subsequence problem

This is a famous computer science problem with various applications in tools such as file diff, bio informatics etc. For more information read this on wiki. Given a set of strings, how do we find the longest common sub-sequence(LCS) among them? For example, LCS{“ATDACG”,”CTDACGA”} is  “TAG”. In this post, we will look at the algorithm…

Generating the counting sequence

Given an integer N, we have to generate the nth sequence of the following pattern. “1” “11” as the previous item contains one instance of 1. “21” as the previous entry contains two 1’s. “1211” as the previous entry contains one 2 and one 1. Following is the program which generates such a sequence. It…