So, i'm trying to do something where it gets a string (let's suppose its 'banana'), and it compares it to an array, let's say ['ananab', 'pottao'] (banana reversed and potato). How would i make it so that it finds all possible combinations of banana (banana, bannaa, ananba, etc..) and compare it with all values of that array?

CodePudding user response：

Iterate over the array, and for each element check if it's an anagram of string.

To see if it's an anagram check Anagrams finder in javascript

CodePudding user response：

Here's one approach. You characterize each target string by building a Map object that contains each character present in the string as a key and the count of the number of occurrences of that character in the string as the value.

So, for the words "hello" and "goodbye", you would have this data structure:

 [
     {
        str: 'hello',
        map: Map(4) { 
           'h' => 1, 
           'e' => 1, 
           'l' => 2, 
           'o' => 1 
        }
      },
      {
        str: 'goodbye',
        map: Map(6) {
          'g' => 1,
          'o' => 2,
          'd' => 1,
          'b' => 1,
          'y' => 1,
          'e' => 1
        }
      }
 ]

In this way, you've characterized the string by the characters present without regard for the order (it's the order you want to disregard).

Then, when you have a candidate string to match, you also characterize it the same way. Then, to check if it's a match, you go through each string in the target and see if the originals are the same length and if the maps are the same length. If neither of those are the same, it can't be a match so you skip it. If those are the same lengths, then you compare the character count for both the source and target and see if they have the same character counts for each character present. If so, they each contain the same characters.

For efficiency, you characterize the comparison words once and retain that array of objects.

Here's a sample implementation:

function characterizeTargets(targets) {
    return targets.map(str => {
        const map = new Map();
        for (let ch of str) {
            let cnt = map.get(ch) | 0;
              cnt;
            map.set(ch, cnt);
        }
        return { str, map };
    });
}

const data = characterizeTargets(["hello", "goodbye"]);

function checkMatch(targets, candidate) {
    const c = characterizeTargets([candidate])[0];
    for (let t of targets) {
        // to be an actual anagram, the originals have to be the same length
        //   and the maps have to be the same size (same number of unique characters)
        let found = true;
        if (t.str.length === c.str.length && t.map.size === c.map.size) {
            for (let [key, val] of t.map.entries()) {
                // see if each item in t is also in c with the same cnt
                if (!c.map.has(key) || c.map.get(key) !== val) {
                    found = false;
                    break;
                }
            }
            if (found) {
                return t.str;
            }
        }
    }
    // didn't find a match
    return null;
}

// See if the arrangement of characters in "olleh" is in the data structure or not
let input = "olleh";
let match = checkMatch(data, input);
if (match) {
    console.log(`"${input}" matches "${match}"`);
} else {
    console.log(`No match found for "${input}"`);
}

If the potential number of targets is large, then you could speed this up a bunch by splitting the characterized targets by length so each length of target is in its own separate array and thus you only ever need to iterate through the array of targets that is already the right length. Since this mechanism already short circuits to check length first, it's probably not a huge savings, but if you have tens of thousands of targets, it might be a useful speed up.