All Possible Combinations and their Substitutions given a string

Waleed Mahmood 0
Viewed 39

I am working on a problem:

Given a password represented as a string and a character map that contains common characters and substitutions, create a list of all possible password combinations that can be created.

Map: {a=@, s=$, E=3, i=!, o=0}

Password String: "password"

Possible outcomes
p@ssword
p@$sword
pa$sword
p@s$word
p@$$word
pa$$word
pas$word
p@ssw0rd
p@$sw0rd
pa$sw0rd
p@s$w0rd
p@$$w0rd
pa$$w0rd
pas$w0rd
passw0rd

My logic so far:

Replace everything except the index you are on. This solution gives the most results but not complete result. It misses about 5 combinations.

My Code so far: it doesnt work and i havent implemented the solution above.

for(int i = 0;i < arr.length;i++){
        for(int j =i; j < arr.length ; j++){
            if(map.containsKey(arr[j])){
                arr[j] = map.get(arr[j]);
                
            }
            //list.add(arr);

        }
        list.add(arr);
    }
hashmap java
1 Answers

Think of the password like a binary number as an incrementing counter:

0000 0001 0010 0011 0100...

Each bit can be 'on' or 'off'. The "bits" of your number are the substitutable letters, and in this case it makes more sense to do the incrementing from left to right.

At any given time, you're either checking a bit, or "carrying" an increment to the next bit. The letters that don't substitute always "carry" automatically. The letters that do substitute increment to the next "value" (you could do this with more than one substitution, like i = {i, I, l, 1}). If you would carry past the "highest value", reset the "bit" to the initial value and "carry" to the next bit that would change. If that bit also carries, keep moving to the right, but if you change a bit, return to the first bit and continue from there.

If the process would go past the end of the word, it would reset the entire value to the initial one so you don't need to print that one and you can terminate the algorithm.

EDIT (by asker request): Let's use your example to illustrate.

In your example, you have two values for five different 'common' characters: 'a', 'e', 'i', 'o', and 's'. Think of each of these as set of ordered lists of 'changeable' characters, such as { <'a', '@'>, <'e', '3'>, ... } and so on. If a letter doesn't have any alternatives, pretend it's in the set too, but it's just a list with a single character in it, like <'p'>. The reason the list is ordered is so that you can go through it systematically, which allows you to know when you've tried all the values. The order doesn't matter, but if it helps you can imagine the "base" character is the common version.

One way to hold that information would be with a map from each possible character (like 'a', '@', 'b', and so on) to a short array that lists the ones you want to interchange. If there's only one version of a character, you don't need to add it. So in the mapping, both 'a' and '@' would be keys for the same sequence of characters <'a', '@'>, and 'p' wouldn't need to be defined at all.

The first string of characters is "password", which you also store as the first word in your set of possible passwords. You also start with an index pointing to the first character in the string.

The algorithm does this. Look at the current index. Check if the value is in the map, and is not the last value in the list the mapping points to: e.g., if the list you find in the map for 'a' or '@' is <'a', '@'>, then 'a' is not the last value, but '@' is the last value.

If it's in the map but it isn't the last value in its list, change the character to the next value in that list: so, 'a' would become '@'. Then set the counter back to zero (even if it's already zero) and continue the loop. Also, every time you return to index zero, you must store the modified string in your set of passwords because it is now a new possible password.

If it IS at the last value (or if it's not in the map, in which case it's always at the last value because there's only one version), you have to carry instead. Change the character back to the first value in the list (so '@' becomes 'a' again, and 'p' doesn't change), and increment the index. Don't add the current word to the set of passwords, though! You aren't done changing it until it returns to index 0, and it's currently the same as a password you've already added.

If the index would go past the end of the string, you've collected all possible passwords (and the string should now be the same as it was initially) so you can stop.

So in your example, we start by looking at index and see that index 0 is not past the end of the string. Then we look at 'p' and it isn't found in the map, so we 'carry': increment the index and repeat the loop. Now we're at index 1 and see 'a', which is in the map, pointing to <'a', '@'>. Since there's at least one character after 'a' in that list, we change 'a' to the next character '@'. Making any change other than a carry means we store this new password, and return to index 0 to repeat the loop. (The next time we see index 1, we'll change it back to 'a', but not store the password because we need to 'carry' and continue walking through the string until we find something new to change or reach the end.)

(Note that I simplified this with the assumption that you always start testing with the "least" character in the list, so you'd test "password" as an initial string, not "p@s$word". It's not too difficult to modify it to work in the other cases, but may be more efficient to just do a first pass through the test string and set it to all 'base' characters, then take that as the initial password.)

Trixie Wolf0
Related