2つの文字列の違いに基づいてすべてのパターンを作成する

Question

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

Answer 1

再帰的な解決策は
時間複雑です：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 

Answer 2

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で終わり、との間のすべてのバリエーションを有するべきです。ここで