3
\$\begingroup\$

As the title says, the problem I had to do sounded something like this:

We are given two words, S1 and S2. We must transform S1 into S2, using the following operations:

insert: insert a character in S1 on whichever index you wish.

delete: delete a character from S1 from whichever index you wish.

replace: replace a character from S1, with whatever character you wish, on whatever index you wish.

All the operations have a cost of 1. At the end of the program, the total cost of all the operations must be minimum, therefore we must use as few operations as possible.

Example:

S1="carte"
S2="antet" 
first operation: delete 'c' at index 0 ; -> S1 = arte
second operation: replace 'r' with n; -> S1 = ante
third operation: add 't' at the end of S1; -> S1=antet

Therefore, we have a total cost of 3.

Here is my code for it:

    package project3;

import java.util.*;

public class Main {
    static String S1 = "antetlllll";
    static String S2 = "antet";

    public static void main(String[] args) {
        StringBuilder sb;
        int c = 0;

        for (int i = 0; i < S2.length(); i++)
            if (i<S1.length())// we make sure that S1 is at least as big as S2
                if(S1.charAt(i)!=S2.charAt(i)){
                if ((i < S1.length() - 1) && (S1.charAt(i + 1) == S2.charAt(i) ) && (S1.charAt(i + 1) != S2.charAt(i+1) ) ) {  // if the char on the next position of S1 is the char we need, we delete the original one
                    sb = new StringBuilder(S1);
                    sb.deleteCharAt(i);
                    S1 = sb.toString();
                    c++;
                } 
                else {  // else, we simply replace it
                    sb = new StringBuilder(S1);
                    String S = "";
                    S = S + S2.charAt(i);
                    sb.replace(i, i+1, S);
                    S1 = sb.toString();
                    c++;
                } }
            else
                if(S1.charAt(i) != S2.charAt(i))
                {  // if S1 is smaller than S2, we simply insert the needed characters into S1
                    sb = new StringBuilder(S1);
                    sb.insert(i, S2.charAt(i));
                    S1 = sb.toString();
                    c++;
                }


        if (S1.length() > S2.length()) {  // at this point S1 has a substring S2 in it. We just remove the extra letters from it.

            int n = S1.length();
            for (int i = S2.length(); i < n; i++) {
                sb = new StringBuilder(S1);
                sb.deleteCharAt(S2.length());
                S1 = sb.toString();
                c++;
            }

        }

        if (S1.length() < S2.length()) {  // at this point S1 has most of S2 characters. We just add the ones still needed.

            int n = S1.length();
            for (int i = n; i < S2.length(); i++) {
                sb = new StringBuilder(S1);
                sb.insert(i,S2.charAt(i));
                S1 = sb.toString();
                c++;
            }

        }

        System.out.println(c);
        System.out.println(S1);
    }

}

Note that when I say things like "S1 bigger than S2", I refer to their lengths.

So I had this problem as an assignment for school, and one of the requirements was that it had to be done using dynamic programming and it had have a complexity of O(m × n) (m=length of S1 ; n=length of S2) at most. Now, I'm new to DP, started doing it today after a bit of research, so I'd like to know if my code meets the two requirements I had.

\$\endgroup\$

closed as off-topic by Tunaki, forsvarir, Ethan Bierlein, janos Jan 10 '17 at 22:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Tunaki, forsvarir, Ethan Bierlein, janos
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Would writing all the character operations on command line deemed as a valid solution? \$\endgroup\$ – coderodde Jan 10 '17 at 18:41
  • \$\begingroup\$ @coderodde Hello. I do not quite understand the question. \$\endgroup\$ – Emy Jan 10 '17 at 18:44
  • \$\begingroup\$ The code doesn't have the expected output on inputs like S1="toast" and S2="test", printing 7 steps, when it should be just 2. The same on S1="tast" and S2="test" (assuming c is the variable counting the steps). \$\endgroup\$ – Tunaki Jan 10 '17 at 18:44
  • \$\begingroup\$ What if your program just print (a shortest) list of operations needed to transform S1 into S2? \$\endgroup\$ – coderodde Jan 10 '17 at 18:45
  • 1
    \$\begingroup\$ @Tunaki You are right, it worked for my two tests and then I got over my head. I'll have to come back with an edit. \$\endgroup\$ – Emy Jan 10 '17 at 18:51
2
\$\begingroup\$

The algorithm is wrong and can't be fixed.

It's not dynamic programming, it's greedy: it iterates over the strings once and decides immediately which operation to perform. Consider some test cases:

                 case 1            case 2            partial read

string 1:        abcde             abcde             abc..
string 2:        abxde             abxcd             abx..

optimal          replace c         insert x          ?
strategy         by x              delete e

Both cases are identical in the first three characters, yet the operations to perform are different. They depend on characters not yet read.

Any algorithm that does not take into consideration the full picture before making a single descision must fail at least one of those test cases. Yours fails the second.

Brute force

The naive way to overcome this problem is a brute force algorithm. Evaluate all possible sequences of operations (insertions, deletions, replacements). When all input was read, output the best sequence.

Dynamic programming

Dynamic programming starts out similar to brute force and evaluates all possible operations, but whenever it finds that two sequences of operations yield the same intermediate result, it keeps (and evaluates further) only one of them.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.