CODEWITHSUNDEEP
javarecursion
kushal
kushal

Reputation: 43

Can Recursion be avoided here? find minimum ways in which one string can be transformed into another

Can Recursion be avoided here? Java code here deals with two strings. find minimum ways in which one string can be transformed into another. at a time we can delete char, add char or replace char from Strings.

public class MinimumWays {

public static int colorSequences(String input1,String input2)
{


    return new MinimumWays().transform(input1, input2);
}

public int transform(String inp1, String inp2){
    int a  = 0; int b=0; int c=0; int result =0;
    if(inp1.length()==0){
        result = inp2.length();
        return result;
    }
    else if(inp2.length()==0){
        result =inp1.length();
        return result;
    }
    if(inp1.substring(0, inp1.length()-1).equals(inp2)||inp1.substring(1, inp1.length()).equals(inp2)){
         a=0;
         return a;
    }
    else{
        a = Math.min(transform(inp1.substring(0, inp1.length()-1), inp2), transform(inp1.substring(1, inp1.length()), inp2) );
    }
    if(inp2.substring(0, inp2.length()-1).equals(inp1)||inp2.substring(1,inp2.length()).equals(inp1)){
         b=0;
         return b;
    }
    else{
        b = Math.min(transform(inp2.substring(0, inp2.length()-1), inp1),transform(inp2.substring(1,inp2.length()), inp1));
    }
    if(inp2.substring(0, inp2.length()-1).equals(inp1.substring(0, inp1.length()-1))|| 
            inp2.substring(0, inp2.length()-1).equals(inp1.substring(1, inp1.length())) || 
              inp2.substring(1, inp2.length()).equals(inp1.substring(0, inp1.length()-1)) ||
                inp2.substring(1, inp2.length()).equals(inp1.substring(1, inp1.length()))){
         c=0;
         return c;
    }
    else{
        int c1 = transform(inp2.substring(0, inp2.length()-1), inp1.substring(0, inp1.length()-1));
        int c2 = transform(inp2.substring(1, inp2.length()), inp1.substring(0, inp1.length()-1));
        int c3 = transform(inp2.substring(0, inp2.length()-1), inp1.substring(1, inp1.length()));
        int c4 = transform(inp2.substring(1, inp2.length()), inp1.substring(1, inp1.length()));
        c = Math.min(Math.min(c1, c2), Math.min(c3, c4));
    }

    result = 1+Math.min(a, Math.min(c, b));
    return result;
}



public static void main(String[] args) {
    String input1 = "sakdh";
    String input2 = "akh";
    System.out.println("Minimum Ways: " + colorSequences(input1, input2));

}

}

Although functionally herenworks fine, but for large Strings(even for 6-7 char) it is taking lot of time. I am not able to figure out any other way to code it. :-(

Upvotes: 1

Views: 175

Answers (2)

Bryce Sandlund
Bryce Sandlund

Reputation: 486

This is edit distance, a common two-dimensional dynamic programming problem. You can solve using recursion and memoization or iteratively.

Try this:

HashMap<List<String>, Integer> memo = new HashMap<List<String>, Integer>();

public int transform(String inp1, String inp2){
{
    List<String> temp = new ArrayList<String>();
    temp.add(inp1);
    temp.add(inp2);
    if (memo.containsKey(temp))
    {
        return memo.get(temp);
    }
    ...

Other people are going to beat me to it but then make sure you store the answer into the HashMap prior to returning. This will make calls to the function return instantly if they have already been calculated, rather than recalculating.

Upvotes: 2

Paco_Da_Taco
Paco_Da_Taco

Reputation: 26

This is known as the "edit distance" problem. There is a more efficient way of solving this problem . Withdynamic programming this problem is O(MN), with M and N being the number of characters in each string. Here is some material on the subject...

http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec6-EditDistance.pdf

Upvotes: 0

Related Questions