Last active
January 5, 2022 23:27
-
-
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
##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