is there any way to do array.includes ignoring order?-CodePudding

I want a function that returns true if the string in the first element of the array contains all of the letters of the string in the second element of the array.

For example, ["hello", "Hello"], should return true because all of the letters in the second string are present in the first, ignoring case.

The arguments ["hello", "hey"] should return false because the string hello does not contain a y.

Lastly, ["Alien", "line"], should return true because all of the letters in line are present in Alien.

Here is the code that i currently have:

function mutation(arr) {

 return arr[0].includes(arr[1]);
}

If i insert arguments such as ['dinosaur', 'dino'] or ['coding', 'ding'] it returns true, which is okay. But if i insert arguments such as ['dinosaur', 'dnour'] or ['coding', 'gnidoc'] it returns false, which i want to return true. What is the simplest way to accomplish this?

CodePudding user response：

The most efficient way to do this test is to convert the first element of the array into a Set and then check that every character in the second element is in the set:

function mutation(arr) {
  first = new Set(arr[0].toLowerCase())
  return [...arr[1].toLowerCase()].every(char => first.has(char))
}

console.log(mutation(['hello', 'Hello']));
console.log(mutation(['hello', 'hey']));
console.log(mutation(['Alien', 'line']));
console.log(mutation(['dinosaur', 'dino']));
console.log(mutation(['dinosaur', 'onion']));
console.log(mutation(['coding', 'ding']));
console.log(mutation(['coding', 'gniDoc']));

Sets are guaranteed (by the specification) to have less than O(n) lookup time (and a reasonable implementation will be a hash table which has O(1) lookup time), so this will be faster than a loop using Array.includes.

Note that this code assumes that mutation(['abc', 'aaa']) should be true as the letter a does occur in the first element of the array (just not 3 times).

CodePudding user response：

You're part of the way there. Ideally you want to iterate over the characters in the second word and check that every character is included in the first word.

Note: to use every (an array method) you need to coerce the string to an array of characters which you can do with Array.from or the spread syntax ([...string])

function check([ first, second ]) {
  return [...second.toLowerCase()].every(char => {
    return first.toLowerCase().includes(char);
  });
}

console.log(check(['hello', 'Hello']));
console.log(check(['hello', 'hey']));
console.log(check(['Alien', 'line']));
console.log(check(['dinosaur', 'dino']));
console.log(check(['dinosaur', 'dnour']));
console.log(check(['coding', 'ding']));
console.log(check(['coding', 'gniDoc']));
console.log(check(['coding', 'fuzzycoding']));

CodePudding user response：

One solution could be with two nested loops but that would be a bit slow.

Time complexity will be O(m*n)

Size of the first element: m, Size of the second element n

This can be improved by using hashMap and indexing the first element letter by counting them.

When letters are counted you can iterate the second element and decrease the counter by comparing it with each letter. When there is no match it will be false.

Finally, you will have the time complexity of O(max(m,n)) which is better than O(m*n)

function mutation([first, second]) {
  const idxs = new Map();
  for(const f of first) {
    const l = f.toLowerCase();
    if(!idxs.has(l)) idxs.set(l, 1);
    else idxs.set(l, idxs.get(l)   1);
  }
  
  for(const s of second) {
  const l = s.toLowerCase();
  const val = idxs.get(l);
    if(val && val > 0) {
       idxs.set(l, idxs.get(l) - 1);
    } else {
      return false;
    }
  }
  
  return true;
}

const tests = [
  [["hello", "Hello"], true],
  [["hello", "hey"], false],
  [["Alien", "line"], true],
  [['dinosaur', 'dino'], true],
  [['dinosaur', 'dnour'], true],
  [['coding', 'gnidoc'], true]
];

for(const [parameters, expected] of tests){
  const result = mutation(parameters);
  console.assert(result === expected, {parameters, expected});
  console.log(parameters, result === expected ? 'PASSED': 'FAILED')
}