Today's problem is checking whether a character array is a subset of another one (when viewed as sets of characters):
Write a function whose first and second inputs are arrays of characters and output is true if every element of the first input is an element of the second input and false otherwise.
For example,
(['t', 'e', 'n', 'n', 'e', 's', 's', 'e', 'e'], ['e', 'n', 's', 't'])
outputs true and
(['h', 'e', 'l', 'l', 'o'], ['a', 'h', 'l', 'e'])
outputs false.
The canonical naïve function runs in O(n * m) time, where n and m are the sizes of the first and second inputs, respectively. Can you write a function that runs in O(n + m) time?
const str1 = ['t', 'e', 'n', 'n', 'e', 's', 's', 'e', 'e'];
ReplyDeleteconst str2 = ['e', 'n', 's', 't']
const str3 = ['a', 'h', 'l', 'e']
let isArraySubset = (stringOne, stringTwo) => {
if(!stringOne || !stringTwo){
console.log('Parameters cannot be empty');
return false;
}
if(stringTwo.length > stringOne.length){
console.log('Second array cannot be longer than the first')
return false;
}
let found = false;
let isSubSet = false;
for(let i = 0; i < stringTwo.length; i++){
found = stringOne.filter((e)=> {
return stringTwo[i] === e;
});
if(found == false){
isSubSet = false;
break}
else{
isSubSet = true;
}
}
return isSubSet;
}
console.log(isArraySubset(str1, str2));
console.log(isArraySubset(str1, str3));
It took me 31 minutes :(. Nee to do better
ReplyDeleteI was being a bit sardonic with that first sentence, chief, lol. Although the algorithm that I shared in the post runs in O(n * m) time, it uses O(1) memory. I came up with another one that runs in O(n + m) time but uses O(m) memory. Yours is the best so far because it runs in O(n + m) time and uses O(1) memory! I liked your use of the "filter" method.
DeleteI now think that it is impossible to write a better algorithm in this sense since we need to know what every character in each array is, yielding a lower bound of O(n + m) on the complexity.
DeleteDon't you think Big O is O(n) where n is the length of the superset? the Filter function will be O(1) in this case
Delete