Posts

Showing posts from March, 2017

Printing All Palindromic Strings in a Matrix

We are given a character matrix and we need to find the list of all the palindromic strings in that matrix starting from the top left corner to the bottom right corner i.e the first character of all the strings must be the top left character in the matrix and the last character must be the bottom right character. The other important condition is that you can only move either towards the right or towards the bottom while tracing a string in the matrix.

Sample Input

Input Matrix is given below

a a a b
b a a a
a b b a

Sample Output

aaaaaa (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (1, 3) -> (2, 3)
aaaaaa (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 3) -> (2, 3)
abaaba (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2) -> (2, 3)

Solution Approach

We can follow a backtrack approach to solve this problem. According to Wikipedia backtracking is defined as :

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, not…

Minimum Number of Hops to Reach the End of an Array

Each element of an array indicates the length of the hop from that particular index. For example : if A[i] is 3 then you can jump to A[i+1] or A[i+2] or A[i+3] from the ith index. The problem states that, find the minimum number of hops required to reach the end of the array. If an element is 0, then it would mean that no other element can be reached from that particular element.

Solution Approach

It can be easily solved using Dynamic Programming. I've used a recursive approach to solve the above given problem. There are a few points to keep in mind before starting with the solution.

1. We need to know when a particular path would end - A particular path would end if you can reach the last element from the current element. i.e i + A[i] >= Length of the Array.

2. We need to find the minimum of the number of hops required from all the elements that can be reached from the current element, recursively.

Solution






In the above program the input is given as 1, 2, 3, 4, 5. The output in…