KMP + Tries, O(n) or not?


  • 0
    L

    I have an idea to this question, but not time to code. Basically like this.

    1. Calculate the KMP look_up table for each words, we can get the shortest string prefix to add this word to be palindrome, actually it's shortest palindrome question. Time complexity (O(n)) Space complexity (O(n));

    2. Create a trie tree for all words, search the prefix from tries tree, Time Complexcity O(k).

    3. special case, the prefix actually is the prefix and prefix + (0 to n) the first letter of words. So tries tree search is non-standard.


  • 0

    Please find some time to code and come back answer your own question. We are curious


  • 0
    P

    I tried Trie structure.

    Putting words in Trie takes a long time O(nk), search words (your step 2) take a long time too O(nn*m (m<<k)), all this add up make the solution not as fast as you expect.

    It is a lot faster than the brute force method. But much slower than the HahsMap method in a hot posts. And my code still ETL.....

    Hopefully you can come up with a much better solution...


Log in to reply
 

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