Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save NeuTrix/7ffad1c8c1a5995d9c22c36709658592 to your computer and use it in GitHub Desktop.
Save NeuTrix/7ffad1c8c1a5995d9c22c36709658592 to your computer and use it in GitHub Desktop.
Find longest word in dictionary that is a subsequence of a given string
##The Challenge
Given a string S and a set of words D, find the longest word in D that is a subsequence of S.
Word W is a subsequence of S if some number of characters, possibly zero, can be deleted from S to form W, without reordering the remaining characters.
Note: D can appear in any format (list, hash table, prefix tree, etc.
For example, given the input of S = "abppplee" and D = {"able", "ale", "apple", "bale", "kangaroo"} the correct output would be "apple"
The words "able" and "ale" are both subsequences of S, but they are shorter than "apple".
The word "bale" is not a subsequence of S because even though S has all the right letters, they are not in the right order.
The word "kangaroo" is the longest word in D, but it isn't a subsequence of S.
Learning objectives
This question gives you the chance to practice with algorithms and data structures.
It’s also a good example of why careful analysis for Big-O performance is often worthwhile, as is careful exploration of common and worst-case input conditions.
## ONE ANSWER
function searchString (String='', Dictionary=[]) {
// sort dictionary by length
Dictionary.sort((a,b) => { return b.length - a.length })
// verify word in substring
function hasSubString(word, str) {
let head = 0;
if (word.length === 0) {
return false
}
for (let i = 0; i < word.length ; i += 1) {
let index = str.indexOf(word[i],head);
if (index < 0 || head > str.length) {
return false
}
head = index + 1;
}
return true
}
// cycle through dictionary, in order of length
for (let i = 0; i < Dictionary.length; i += 1) {
if (hasSubString(Dictionary[i], String)) {
return `The longest word is "${Dictionary[i]}"`
}
}
return `There are no substrings for this Dictionary`
}
### test
let D = ['larry', 'gingerbreadmuffin', 'egg', 'bibles', 'love']
let S = "biagedinsbgeerabredagfeafadsmdfufdfdfki ng"
console.log(searchString(S,D))// "gingerbreadmuffin"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment