CODEWITHSUNDEEP
javastring
Mr.Fireman
Mr.Fireman

Reputation: 554

Creating all variations based on the differences of two Strings

I do have a function waiting two Strings. I would like to return with a list of words containing all of the possible variations, which can be created based on the differences.

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

So far I have created the function which counts the differences, and saves their locations. Do you have any idea how to continue?

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

Upvotes: 1

Views: 459

Answers (2)

abhaybhatia
abhaybhatia

Reputation: 629

Here is a recursive solution
Time Complexity : 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;
}

Test Code:

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

Output: 

igis
egis
iges
eges

Upvotes: 2

Topological Sort
Topological Sort

Reputation: 2866

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

When this is done, toReturn should start with q and end with qW, and have all variations between.

Upvotes: 0

Related Questions