Find longest subsequence s of String in a dictionary

Question

Find the longest subsequence s of a String such as "abccdde" and given a dictionary {"ab","add","aced"} . the result of above example is "add"

I was asked in an interview, I gave an answer using trie tree and worst case is O(n*m) ,and n is length of s , m is length of dictionary. But my average cost should be very low. I fail the interview because the interviewer thought my solution was not the best one. Does anyone have a better idea?

Answer 1

You can create a graph, then the vertices are your alphabet. For each word in your dictionary you'll add the first character in your graph something like:

G[word[0]].add({word, 0})

Then when you're visiting your text for each letter you visit the adyacency list for that letter. For each item in your list, you should add the next character for that word.

With your example:

S = "abccdde", D = {"ab","add","aced"}

First step:

G = {{'a', [{"ab", 0}, {"add", 0}, {"aced", 0}]}}

For each character in S

• character = 'a' -> S[0]

You visit the list for that character

[{"ab", 0}, {"add", 0}, {"aced", 0}]

and update your graph

G = {{'b', [{"ab", 1}]}, {'d', ["add", 1]}, {'c', [{"aced", 1}]}}

• character 'b' -> S[1]

You visit the list for that character

[{"ab", 1}]

and update your graph

G = {{'d', ["add", 1]}, {'c', [{"aced", 1}]}}

as you finished "ab" you can try to improve your answer.

• character 'c' -> S[2]

You visit the list for that character

[{"aced", 1}]

and update your graph

G = {{'d', ["add", 1]}, {'e', [{"aced", 2}]}}

• character 'c' -> S[3]

There is not list for that character then you continue with the next character

• character 'd' -> S[4]

You visit the list for that character

["add", 1]

and update your graph

G = {{'d', ["add", 2]}, {'e', [{"aced", 2}]}}

...