Skip to content

Instantly share code, notes, and snippets.

@clamstew
Created March 7, 2022 04:58
Show Gist options
  • Save clamstew/7a3781a311ed7aa7374414d1e6581596 to your computer and use it in GitHub Desktop.
Save clamstew/7a3781a311ed7aa7374414d1e6581596 to your computer and use it in GitHub Desktop.
trying out the Dictionary and isInDict() function from youtube video
const Mocha = require('mocha');
const assert = require('assert');
const mocha = new Mocha();
// Bit of a hack, sorry!
mocha.suite.emit('pre-require', this, 'solution', mocha);
/*
from: https://www.youtube.com/watch?v=yju4zwKSriI
Input (array of words):
"cat, "car", "bar"
// do as much work as possible in the setup
// function to optimize the isInDict func
function setup(input)
// optimal is likely O(n) time
// but maybe could be constant time of O(1)
// if you have 1 input like "cat" and it does
// one operation to find it
function isInDict(word)
setup(["cat, "car", "bar"])
isInDict("cat") // true
isInDict("bat") // false
*/
const sampleWords = ["cat", "car", "bar"];
const enUSAlpha = (() => {
const caps = [...Array(26)].map((val, i) => String.fromCharCode(i + 65));
return caps.map(letter => letter.toLowerCase());
})();
const dictionary = {};
// this could be closer to O(n * k)
const setup = (words) => {
words.forEach(word => {
const chars = word.split("");
let lastDictionaryLevel = dictionary;
chars.forEach((char, i) => {
if (!lastDictionaryLevel[chars[i]] && !chars[i + 1]) {
lastDictionaryLevel[chars[i]] = word;
} else if (!lastDictionaryLevel[chars[i]]) {
lastDictionaryLevel[chars[i]] = {};
}
lastDictionaryLevel = lastDictionaryLevel[chars[i]];
});
});
console.log("dictionary", dictionary)
};
const isInDict = (word) => {
let currentDictLevelFound = dictionary;
let possibleCurrentDictLevels = dictionary;
let wordFound = false;
let possibleCurrentDictLevel = null;
for (let i = 0; i < word.length; i++) {
const char = word[i];
if (char === "*") {
possibleCurrentDictLevels = enUSAlpha.map(char => currentDictLevelFound && currentDictLevelFound[char]).filter(entry => !!entry);
if (!possibleCurrentDictLevels || possibleCurrentDictLevels.length === 0) break;
// possibleCurrentDictLevel = null;
console.log("possibleCurrentDictLevels",possibleCurrentDictLevels)
for (let j = 0; j <= possibleCurrentDictLevels.length; j++) {
possibleCurrentDictLevel = possibleCurrentDictLevels[j];
console.log('possibleCurrentDictLevel',possibleCurrentDictLevel)
if (possibleCurrentDictLevel && typeof possibleCurrentDictLevel === "string") {
wordFound = true;
}
}
} else {
currentDictLevelFound = currentDictLevelFound[char];
if (typeof currentDictLevelFound === "string") {
wordFound = true;
}
}
}
/*
if char === "*"
then search all 26 letters as char
*/
console.log("wordFound", wordFound)
return wordFound;
}
// "cat, "car", "bar"
// setup();
describe('Test suite', function() {
setup(sampleWords);
describe('when word in dict', function() {
it("it returns true", () => {
assert.equal(isInDict("cat"), true)
})
})
describe('when word is NOT in dict', function() {
it("it returns false", () => {
assert.equal(isInDict("bat"), false)
})
})
describe('when word WITH WILDCARD is in dict', function() {
it("it returns TRUE", () => {
assert.equal(isInDict("*at"), true)
})
})
describe('when word WITH WILDCARD is NOT in dict', function() {
it("it returns TRUE", () => {
assert.equal(isInDict("cr*"), false)
})
})
})
mocha.run()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment