Is there a way to replace letters with numbers/symbols in JS and show each possible outcome?

user_10778310 0
Viewed 307

I am working on a project where I need to covert a list of words into all possible options using symbols / numbers.

I actually want functionality pretty much identical to This Stack Overflow Question, however, it is written in Python using the intertools.product method. I do not know how to convert this into JS.

For example:

let givenInput= 'hello';
let expectedOutput = ["hello", "h3llo", "he1lo", "hel1o", "hell0", "h31lo", "h3l1o", "h3ll0", "he11o", "he1l0", "hel10", "h311o", "h31l0", "h3l10", "he110", "h3110"];

I tried having an object with the replacements I am expecting:

let REPLACE = {
'o': '0',
'e': '3',
'l': '1',
'a': '@'
}

I have tried a more manual method, where I replace one letter, add that option to an array, change another, add that to the array, etc. But I need to know too much about the string I am manipulating.

I have also tried to just use string.replace() using a regex, but that only really seems to work when I am replacing ALL of one character with another one and not one at a time.

The end goal of this is a generator to generate a list of words I do not want to be allowed in a name creator. So like, I want to exclude bad words, and all possible letter-replacement versions of those words.

combinations javascript string
2 Answers

You could build an array of replacement characters and get the cartesian product.

const
    input= 'hello',
    REPLACE = { o: '0', e: '3', l: '1', a: '@' },
    result = Array
        .from(input, c => c in REPLACE ? [c, REPLACE[c]] : [c])
        .reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []))
        .map(a => a.join(''));
        
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

user_14476750

Imagine this approach:

  1. Take the first letter of the input. Either it can or can't be substituted. This creates a list of options for the first letter which contains either one or two elements (either the letter alone, or the letter along with its substitution)
  2. Take all the letters beyond the first letter, and get their permutations (in other words, solve this problem for all letters beyond the 1st)
  3. If the options for the first letter includes just one option, simply prepend that character to each result in the list of permutations for the letters beyond the first (and you're done!) If there are two options for the first letter return the list of beyond-the-first-letter-permutations doubled; but for every item in the first half of that list prepend the first initial-letter-option, and for every item in the second half prepend the second initial-letter option.

It may seem magical that this solution requires itself to already be defined (in step #2), but this is no problem for many programming languages.

Here we'll define permuteSubstitutions(str, subs) as the function which solves this problem. Now as we're implementing the full solution we can gloss over step #2 by simply referring to permuteSubtitutions.

let permuteSubstitutions = function*(str, subs) {
  
  // There's only one possible permutation for the empty string
  if (!str) { yield ''; return; }
  
  // Either 1 or 2 options for the head:
  // - Only the leading character, if it can't be substituted,
  // - or the leading character and substituted character
  let heads = subs.hasOwnProperty(str[0])
    ? [ str[0], subs[str[0]] ]
    : [ str[0] ];
  
  // `str`, minus its first letter
  let tail = str.slice(1);
  
  // For each possible leading letter yield a result for each permutation
  // of the tailing letters. This works because of the definition we gave
  // to `permuteSubstitutions`! We'll get every permutation of the `tail`,
  // and combine it with the possibilities for `head`.
  for (let permutedTail of permuteSubstitutions(tail, subs)) {
    for (let head of heads) {  
      yield head + permutedTail;
    }
  }
  
};

let results = permuteSubstitutions('hello', {
  'o': '0',
  'e': '3',
  'l': '1',
  'a': '@'
});
for (let result of results) console.log(result);

You may have noticed that every substitutable letter doubles the number of resulting permutations. For that reason I've implemented this for you as a function*(...){...}, which will have no issue returning a vast number of results (unlike a buffered/Array-based approach). You should still be careful with this code, as if someone manages to get your code to verify the term oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo your cpu may wind up performing 2^100 iterations, and that will make it quite sad.

Note that if you are trying to detect terms that may contain homoglyphs you will have much more success "normalizing" words and directly comparing them against your dictionary. Just replace all "homoglyphic" letters with their base meaning (e.g. transform 4 -> A, @ -> A, 1 -> L, 3 -> E, etc.) This would transform a string like:

1@NGU4G3

into:

LANGUAGE

allowing the word to be directly compared to a dictionary. This overall will have a much more reasonable runtime.

user_8309050
Related