Longest word in dictionary formed by deleting some characters

  • 0

    Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
    eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"

    I was thinking of the following approach,

    1. Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
    2. For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
      This should take O( N * k) where N is length of S.

    Please let me know if my approach is okay? Can we do it with dp/backtracking without a trie similar to word break ii?

  • 0

  • 1

    How about putting the string in a HashMap with the index of every character as value of the character key.

    You can then go through every string and check if it's valid, by checking that the index of every next char in the string is greater than the previous.

    Eg hmap.get(a) < hmap.get(l) < hmap(e) then its valid.

    Now, check the length of "ale" against an int min and update min accordingly.

    Time complexity should be less than O(N*k) I think.

  • 4

    It can be done in O (K * L * log (N)), reducing to check if it is a valid subsequence.
    K = number of words in dict
    N = size of S
    L = length of the greatest string in dict

    We pre-process the string S, in the following way (considering all characters are [a-z]):
    S = aabccbba, we need to vector <vector <int>> pos [3] (for a, b and c)
    Pos ['a'] = 0, 1, 7
    Pos ['b'] = 2, 5, 6
    Pos ['c'] = 3, 4
    This array stores the indexes of each character in a separate container for each character.

    Giving this array we can do a binary search for all characters in word [i], since it is an increasing sequence of indexes.
    Now, for each word [i] in dict, do the following:
    We start with an idxInS = -1;
    For each word [i] [j], we seek for the lowest value in pos [word [i] [j]] that is greater than idxInS.
    If there is a valid index, update idxInS.
    Otherwise, it is impossible.

    So, this way we can find all valid words and get the greatest word.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.