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

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

完成后，返回应该以q开始，以qw结束，并且在这两者之间有所有的变化。