根据两个字符串的差异创建所有变体

Question

我有一个等待两个字符串的函数。我想要 return 包含所有可能变体的单词列表，可以根据差异创建这些变体。

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

Answer 1

for (int i = 0; i < q.length(); i++) //as before, but a little simplified...
    if (q.charAt(i) != q.charAt(i)) 
         locations.add(i);

//Now we're going to create those variations.

toReturn.add(q);  //Start with the first string

for each location we found
   Additions = a new empty list of Strings
   for each element in toReturn
      create a new String which is a copy of that element
      alter its location-th character to match the corresponding char in qW
      append it to Additions
   append Additions to toReturn

完成后，toReturn 应该以 q 开始，以 qW 结束，并且具有两者之间的所有变化。

Answer 2

这是一个递归的解决方案
时间复杂度：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

根据两个字符串的差异创建所有变体

Creating all variations based on the differences of two Strings

java

string

compare

variation

difference