Skip to content

Instantly share code, notes, and snippets.

@marvinsjsu
Created August 8, 2019 20:30
Show Gist options
  • Save marvinsjsu/19f2150794122ed6cdbc132d917dac38 to your computer and use it in GitHub Desktop.
Save marvinsjsu/19f2150794122ed6cdbc132d917dac38 to your computer and use it in GitHub Desktop.
longest chain count
function longestChain(words) {
let sortedWords = words.sort((a, b) => b.length - a.length);
let wordSet = new Set(sortedWords);
let longestChain = 0;
function funcRecur(wordRecur, count) {
// console.log('wordRecur: ', wordRecur, ' count: ', count);
if (wordRecur.length <= 1) {
// console.log('this is what gets returned: ', count);
return count;
};
let shortened = '';
let foundPath = false;
for (let i = 0; i < wordRecur.length; i++) {
shortened = wordRecur.slice(0, i) + wordRecur.slice(i + 1, wordRecur.length);
if (wordSet.has(shortened)) {
foundPath = true;
return funcRecur(shortened, count + 1);
}
}
if (!foundPath) {
return count;
}
}
let countForWord = 0;
for (let word of sortedWords) {
countForWord = funcRecur(word, 1);
console.log(`${word}: `, countForWord);
longestChain = countForWord > longestChain ? countForWord : longestChain;
}
return longestChain;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment