1

2 つの文字列を待機する関数があります。違いに基づいて作成できるすべての可能なバリエーションを含む単語のリストを返したいと思います。

getAllVersions('cso','cső'); //--> [cso, cső]
getAllVersions('eges','igis'); //--> [eges, igis, egis, iges]

これまでのところ、違いを数え、その場所を保存する関数を作成しました。続行する方法はありますか？

public ArrayList<String> getAllVersions(String q, String qW) {
            int differences = 0;
            ArrayList<Integer> locations = new ArrayList<>();
            ArrayList<String> toReturn = new ArrayList<>();

            for (int i = 0; i < q.length(); i++) {
                if (q.charAt(i) != q.charAt(i)) {
                    differences++;
                    locations.add(i);
                }
            }  
                   toReturn.add(q);
                   toReturn.add(qW);
             for (int i = 0; i < q.length(); i++) {
               for (int j = 0; j < q.length(); j++) {

               }
             }
            return toReturn;
        }
    }
4

2 に答える 2

2

ここに再帰的な解決策があります
Time Complexity : O(n)

public List<String> allVariants(String x, String y) {
    if ((x == null || x.isEmpty()) && (y == null || y.isEmpty())) {
        return new ArrayList<String>();
    }
    List<String> l = new ArrayList<String>();
    if (x == null || x.isEmpty()) {
        l.add(y);
        return l;
    }
    if (y == null || y.isEmpty()) {
        l.add(x);
        return l;
    }
    char xc = x.charAt(0);
    char yc = y.charAt(0);
    List<String> next = allVariants(x.substring(1), y.substring(1));
    if (next.isEmpty()) {
        l.add(xc + "");
        if (xc != yc) {
            l.add(yc + "");
        }
    } else {
        for (String e : next) {
            l.add(xc + e);
            if (xc != yc) {
                l.add(yc + e);
            }
        }
    }
    return l;
}

テストコード:

public static void main(String[] args) {
    List<String> l = new Test().allVariants("igis", "eges");
    for (String x : l) {
        System.out.println(x);
    }
}

出力：

igis
egis
iges
eges
于 2016-03-28T17:31:24.013 に答える