Rotated String conundrum

Problem Statement: You have an original string and its rotated version as input. (Eg. Original string = hello, Rotated string = llohe) You need to tell how many places the original string needs to be rotated by to get the rotated string.

You can come up with multiple approaches here, all of which are bullshit and not efficient. I have only been able to find a single method which gives me acceptable efficiency.

Solution: You should append the rotated string at the end of another instance of the rotated string and then find the original string in it. And your answer will be length of string minus the starting position of the found substring (original string)

Eg. llohellohe (appended llohe after llohe )

So I search fot he original string ‘hello’. This gives me the starting position 3 (index from 0). So rotation = (5-3) = 2

EDIT: You can implement this in a better way by indexing the original string as i%string.length where i will range from 0 to twice the string length. You are effectively going twice through the rotated string while searching for the substring. – Contributed by Sanjoy (due credits )

Pretty easy, eh?

Edit Distance using Dynamic Programming

In the previous post, I discussed a recursive method for finding the Edit Distance (once again, refer previous post for details) between two strings. Some of you might have noticed that the recursive function (in this case) could just as easily be utilized in a Dynamic Programming method.

However, we would be increasing the space complexity by using a 2D array (as is the case with many Dynamic Programming problems). The time complexity would reduce to O( length of String1 * length of String2 ). Since the whole logic has already been explained in the previous post, here is the algorithm.

int EditDistance( String1, String2 )

{

m = String1.length

n = String2.length

For i=0 , i<=m , i++

V[i][0] = i

For i=0 , i<=n , i++

V[0][i] = i

//cells in first row and column of temporary 2D array V set to corresponding number

For i=1 , i<=m , i++

{

For j=1 , j<=n , j++

{

If ( String1[i-1] == String2[j-1] )

V[i][j]=V[i-1][j-1]

Else

V[i][j] = 1 + min( min(V[i][j-1], V[i-1][j]), V[i-1][j-1])

}

}

RETURN V[m][n] //last element of 2D array (last row, last column)

}

So the logic remains the same. The only difference is that we avoid the use of system stack and instead store previous results in a 2D array. Neat!

Edit Distance between two strings (using Recursion)

Problem Statement: Find the edit distance between two given strings. Edit distance is the minimum number of operations required to modify one string into the second one or vice versa. The operations allowed are as follows:

1. Delete a character

2. Replace a character with another one

3. Insert a character

For example,

String 1 = Hello

String 2 = Helo

The edit distance is 1 here, since we can convert 2 -> 1 by inserting an ‘l’.

Recursion is a Brute-Force method to solve this because it basically checks all the possibilities and finds the minimum number of operations. I am discussing this method as it is an exhaustive approach and gives you an idea of what edit distance is. So here is how the algorithms looks:

int EditDistance ( String1, String2, m, n )

{

If ( String2.length == n ) return (String1.length-m)

If ( String1.length == m) return (String2.length-n)

If ( String1[m] == String2[n] ) return EditDistance(String1, String2, m+1, n+1 )

If ( String1[m] != String2[n] )

   return 1+min(min(EditDistance(String1, String2, m, n+1), EditDistance(String1, String2, m+1, n)), EditDistance(String1, String2, m+1,n+1))

}

That is all! Let me explain it a little. What we are doing is moving forward through the strings until the end of any one is found. If the end is found (i.e., m/n match length) we return the length of the other string minus this string’s length as those many operations will be required from that point on. If the characters at the same position are same, then there is no problem. We move ahead. If they are not the same, then we check if the next character in the other array match this one (for detecting a required deletion/insertion).

There is a better approach, using Dynamic Programming for this problem. I’ll discuss it in the next post!