1

ここで再帰を回避できますか？ここでの Java コードは 2 つの文字列を扱います。ある文字列を別の文字列に変換できる最小限の方法を見つけます。一度に char を削除したり、char を追加したり、文字列から char を置き換えたりできます。

パブリッククラスの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));

}

}

機能的には問題なく動作しますが、大きな文字列 (6 ～ 7 文字の場合でも) には多くの時間がかかります。それをコーディングする他の方法を理解することはできません。:-(

4

2 に答える 2

2

これは編集距離であり、2 次元の動的計画法の一般的な問題です。再帰とメモ化、または反復を使用して解決できます。

これを試して：

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);
    }
    ...

他の人が私を打ち負かすつもりですが、戻る前に必ず答えを HashMap に保存してください。これにより、再計算するのではなく、既に計算されている場合、関数の呼び出しが即座に返されます。

于 2013-10-28T21:08:10.347 に答える
0

これは「編集距離」問題として知られています。この問題を解決するより効率的な方法があります。動的プログラミングでは、この問題は O(MN) であり、M と N は各文字列の文字数です。ここに主題に関するいくつかの資料があります...

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

于 2013-10-28T21:04:45.480 に答える