Hjælp til at "oversætte" JS til Java

Funktionen beregner det mindste antal tegn, som skal ændres, som der  skal til for at ændre string2 til string1. Fx string1 = hejhej23hej  string2 = hejhejhej.
Funktionen returnerer i dette tilfælde 2

Mit forslag:
import java.util.*;

public class Main
{ 
    public static void main(String args[])
    {
        System.out.println("[test][test]    = " + diffStr("test", "test"));
        System.out.println("[qwerty][qwert]  = " + diffStr("qwerty", "qwert"));
        System.out.println("[qwert][qwerty]  = " + diffStr("qwert", "qwerty"));
        System.out.println("[qwerty][asdfgh] = " + diffStr("qwerty", "asdfgh"));
        System.out.println("[asdfgh][qwerty] = " + diffStr("asdfgh", "qwerty"));       
    }

    public static int diffStr(String input1, String input2)
    {
        HashMap map = new HashMap();
        int retVal = 0;
       
        for(int i=0;i<input1.length();i++)
        {
            if(map.containsKey(new Character(input1.charAt(i))))
            {
                int temp = ((Integer)map.get(new Character(input1.charAt(i)))).intValue();
                temp++;
                map.put(new Character(input1.charAt(i)), new Integer(temp));
            }
            else
            {
                map.put(new Character(input1.charAt(i)), new Integer(1));
            }
        }       

        for(int i=0;i<input2.length();i++)
        {
            if(map.containsKey(new Character(input2.charAt(i))))
            {
                int temp = ((Integer)map.get(new Character(input2.charAt(i)))).intValue();
                temp--;
                map.put(new Character(input2.charAt(i)), new Integer(temp));
            }
            else
            {
                map.put(new Character(input2.charAt(i)), new Integer(1));
            }
        }
       
        Iterator iter = map.values().iterator();
        while(iter.hasNext())
        {
            int temp = ((Integer)iter.next()).intValue();
            if(temp != 0)
            {
                retVal += Math.abs(temp);
            }
        }
       
        return retVal;
    }
}

Output:
[test][test]    = 0
[qwerty][qwert]  = 1
[qwert][qwerty]  = 1
[qwerty][asdfgh] = 12
[asdfgh][qwerty] = 12


Jeg er spændt på at se andre løsninger.

det ser desværre ikke ud til at virke. [qwerty][asdfgh] burde returnere 6 det samme burde [asdfgh][qwerty]. Men ellers passer de andre.

Ja, jeg har set fejlen. Jeg er ved at rette.

Hvad skal returværdien være ved:
[a][bbb]

3 eller hvad ?

ja

lidt flere eksempler:

[internet explorer][netscape] = 12
[sodavand][danmak] = 6
[eksperten][kuglepen] = 6

kuglepen:
k = 1
u = 1
g = 1
l = 1
e = 2
p = 1
n = 1

eksperten:
e = 3
k = 1
s = 1
p = 1
r = 1
t = 1
n = 1

For at kuglepen skal blive til eksperten mangler der:
e = 1
s = 1
r = 1
t = 1
Hvilket giver 4

Hvordan får du det til 6 ??

Nå, men i tilfælde af at 4 er korrekt så kig lidt på dette:

import java.util.*;

public class Main
{ 
    public static void main(String args[])
    {
        System.out.println("    [hejhej23hej][hejhejhej] = " + diffStr("hejhej23hej", "hejhejhej") + "\t(2)");
        System.out.println("                [test][test] = " + diffStr("test", "test") + "\t(0)");
        System.out.println("              [qwerty][qwert] = " + diffStr("qwerty", "qwert") + "\t(1)");
        System.out.println("              [qwert][qwerty] = " + diffStr("qwert", "qwerty") + "\t(1)");
        System.out.println("            [qwerty][asdfgh] = " + diffStr("qwerty", "asdfgh") + "\t(6)");
        System.out.println("            [asdfgh][qwerty] = " + diffStr("asdfgh", "qwerty") + "\t(6)");
        System.out.println("                    [a][bbb] = " + diffStr("a", "bbb") + "\t(3)");
        System.out.println("                    [bbb][a] = " + diffStr("bbb", "a") + "\t(3)");
        System.out.println("[internet explorer][netscape] = " + diffStr("internet explorer", "netscape") + "\t(12)");
        System.out.println("          [sodavand][danmak] = " + diffStr("sodavand", "danmak") + "\t(6)");
        System.out.println("        [eksperten][kuglepen] = " + diffStr("eksperten", "kuglepen") + "\t(6)"); 
    }

    public static int diffStr(String input1, String input2)
    {       
        int retVal = 0;
        int len1 = input1.length();
        int len2 = input2.length();
       
        HashMap map = new HashMap();

        for(int i=0;i<len2;i++)
        {
            char ch = input2.charAt(i);
            if(map.containsKey(new Character(ch)))
            {
                int temp = ((Integer)map.get(new Character(ch))).intValue();
                temp++;
                map.put(new Character(ch), new Integer(temp));
            }
            else
            {
                map.put(new Character(ch), new Integer(1));
            }
        }

        for(int i=0;i<len1;i++)
        {
            char ch = input1.charAt(i);
            if(map.containsKey(new Character(ch)))
            {
                int temp = ((Integer)map.get(new Character(ch))).intValue();
                temp--;
                if(temp == 0)
                {
                    map.remove(new Character(ch));
                }
                else
                {
                    map.put(new Character(ch), new Integer(temp));
                }
            }
            else
            {
                retVal++;
            }
        }
        if(len2 > len1)
        {
            retVal += len2 - len1;
        }
   
        return retVal;
    }
}

Output:
        [hejhej23hej][hejhejhej] = 2      (2)
                        [test][test] = 0      (0)
                  [qwerty][qwert] = 1      (1)
                  [qwert][qwerty] = 1      (1)
                [qwerty][asdfgh] = 6      (6)
                [asdfgh][qwerty] = 6      (6)
                            [a][bbb] = 3      (3)
                            [bbb][a] = 3      (3)
[internet explorer][netscape] = 12      (12)
            [sodavand][danmak] = 4      (6)
          [eksperten][kuglepen] = 4      (6)

shit...mit spm kan vist forstås på flere måder :-( 
fx [eksperten][kuglepen]

  k u g l e p e n
e k s p e r t e n

her kan du se at det første 'e' i eksperten skal slettes (=1 operation) og 'spert' skal erstattes af 'uglep'(=5 operationer). Ialt 6 operationer
Men jeg kan desværre sagtens se at spm kan forstås på den måde du forstår det på...min fejl
Grundlæggende er det tilladt at slette, erstatte og indsætte bogstaver.

public class WordToWord {
    public static int calc(String w1, String w2) {
        if((w1.length() == 0) && (w2.length() == 0)) {
            // done
            return 0;
        }
        if((w1.length() > 0 )  &&
          (w2.length() > 0) &&
          (w1.charAt(0) == w2.charAt(0))) {
              // match
            return calc(w1.substring(1), w2.substring(1));
        }
        int d,i,u;
        if(w1.length() > 0) {
            // delete 1 char in w1
            d = 1 + calc(w1.substring(1), w2);
        } else {
            d = Integer.MAX_VALUE;
        }
        if(w2.length() > 0) {
            // insert 1 char in w1
            i = 1 + calc(w1, w2.substring(1));
        } else {
            i = Integer.MAX_VALUE;
        }
        if((w1.length() > 0) && (w2.length() > 0)) {
            // update 1 char in w1
            u = 1 + calc(w1.substring(1), w2.substring(1));
        } else {
            u = Integer.MAX_VALUE;
        }
        return Math.min(d, Math.min(i, u));
    }
    private static void test(String w1, String w2) {
        System.out.println(w1 + "->" + w2 + " = " + calc(w1, w2));
    }
    public static void main(String[] args) {
        test("hejhej23hej", "hejhejhej");
        test("qwerty", "qwert");
        test("eksperten", "kuglepen");
    }
}

output:

hejhej23hej->hejhejhej = 2
qwerty->qwert = 1
eksperten->kuglepen = 6

Fint, jeg tror jeg nøjes med at oversætte dit.. :-)

import java.util.*;

public class Main
{ 
    public static void main(String args[])
    {
        System.out.println("    [hejhej23hej][hejhejhej] = " + diffStr("hejhej23hej", "hejhejhej") + "\t(2)");
        System.out.println("                [test][test] = " + diffStr("test", "test") + "\t(0)");
        System.out.println("              [qwerty][qwert] = " + diffStr("qwerty", "qwert") + "\t(1)");
        System.out.println("              [qwert][qwerty] = " + diffStr("qwert", "qwerty") + "\t(1)");
        System.out.println("            [qwerty][asdfgh] = " + diffStr("qwerty", "asdfgh") + "\t(6)");
        System.out.println("            [asdfgh][qwerty] = " + diffStr("asdfgh", "qwerty") + "\t(6)");
        System.out.println("                    [a][bbb] = " + diffStr("a", "bbb") + "\t(3)");
        System.out.println("                    [bbb][a] = " + diffStr("bbb", "a") + "\t(3)");
        System.out.println("[internet explorer][netscape] = " + diffStr("internet explorer", "netscape") + "\t(12)");
        System.out.println("          [sodavand][danmak] = " + diffStr("sodavand", "danmak") + "\t(6)");
        System.out.println("        [eksperten][kuglepen] = " + diffStr("eksperten", "kuglepen") + "\t(6)"); 
    }

    public static int diffStr(String string1, String string2)
    {       
        int m[][] = new int[string1.length()+1][];
        int i, j;
       
        for(i=0; i < string1.length() + 1; i++)
            m[i] = new int[string2.length()+1];
       
        m[0][0] = 0;
       
        for(j=1; j <= string2.length(); j++)
            m[0][j] = m[0][j-1] + 1;
       
        for(i=1; i <= string1.length(); i++)
        {
            m[i][0] = m[i-1][0] + 1;
            for(j=1; j <= string2.length(); j++)
            {
                int diag = m[i-1][j-1];
                if( string1.charAt(i-1) != string2.charAt(j-1) )
                    diag++;
               
                m[i][j] = Math.min( diag, Math.min( m[i-1][j]-0 + 1, m[i][j-1]-0 + 1 ) );
            }
        }
        return m[string1.length()][string2.length()];
    }
}

Output:
        [hejhej23hej][hejhejhej] = 2      (2)
                          [test][test] = 0      (0)
                    [qwerty][qwert] = 1      (1)
                  [qwert][qwerty] = 1      (1)
                  [qwerty][asdfgh] = 6      (6)
                  [asdfgh][qwerty] = 6      (6)
                              [a][bbb] = 3      (3)
                              [bbb][a] = 3      (3)
[internet explorer][netscape] = 12      (12)
            [sodavand][danmak] = 6      (6)
          [eksperten][kuglepen] = 6      (6)

Den er jo også:
  - garanteret ekvivalent med JavaScript koden
  - meget hurtigere end min kode fordi den er O(n^2) mod O(3^n)

Jeg kan bare ikke gennemskue logikken i den.

jeg kan heller ikke gennemskue den :-) hvordan du kan se at
soreno's kode er O(n^2)?

Et 2D array og en for-løkke inden i en for-løkke - det må være O(n^2).

Jeg kan hverken genneskue logikken i JavaScriptkoden eller Arnes kode.

I hvilken sammenhæng skal det bruges ?

det skal bruges til at sammenligne 2 gen-koder, og finde forskellen mellem disse.  Jeg har også meget svært ved at finde logikken javascript-koden som jeg har fundet. Jeg syntes ikke den giver mening, men den virker :-)

Min kode er faktisk rimelig simpel. Den prøver alle muligheder.
Hvis der er 2 bogstaver som ikke matcher har man 3 muligheder:
delete, insert og update. Og programmet prøver alle 3 muligheder
for alle positioner via rekursion. Det skal virke. Men koster
også.

Den anden algoritme virker tilsyneladende også. Men spørgsmålet
er hvorfor den virker.

http://www.csse.monash.edu.au/~lloyd/tildeStrings/Alignment/92.IPL.html

her kan læses lidt om hvordan det virker. Men jeg fatter det squ stadig ikke. Hvis en af jer ser systemet i det, må i meget gerne skrive det....Har det trods alt bedst når jeg fatter teorien bag :-)

Hm.

Mit approach må svare til algoritme 1.

JS til algoritme 2.

Og algoritme 3 er så den bedste.

Det er ikke ligfrem nogen let tilgængelig artikel.

Tak for hjælpen