java基于两个字符串的差异创建所有变体

Question

我确实有一个函数在等待两个字符串。我想返回一个包含所有可能变化的单词列表，可以根据差异创建

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结尾，并且所有变量都在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