Sunday, May 3, 2015

Number of steps required to convert string 1 to string2 when only bring character to first index operation is giving

Problem
Given 2 strings - s1 and s2, when only 1 operation is allowed - Moving character at a time but only to the first position.

Example
Example 1
Input
s1 = abcd
s2 = bacd

Output
Ans = 1
Reason, just move b forward and we get it.

Example 2
Input
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Output
Ans =7
Explanation
A = (a)b(cd)e(f)g(hij)
B = ahdjcifbeg
Characters b,e,g are in the order, rest characters have to brought first.


Solution

This is a DP problem,  LCS of the 2 strings is adf, and rest of the character are moved forward, and rest of the characters will be moved forward.

0 comments:

Post a Comment