Création de toutes les variantes basées sur les différences de deux chaînes

Question

J'ai une fonction en attente de deux chaînes. Je voudrais revenir avec une liste de mots contenant toutes les variations possibles, qui peuvent être créées en fonction des différences.

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

Jusqu'ici j'ai créé la fonction qui compte les différences et enregistre leurs emplacements. Avez-vous une idée de la façon de continuer?

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

Voici une solution récursive
Complexité: 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; 
} 

Code d'essai:

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

Sortie:

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 

Lorsque cela est fait, toReturn devrait commencer par q et se terminer par qW, et ont toutes les variations entre.