Longest Common Prefix


  • 0

    Click here to see the full article post


  • 0
    L

    Approach #4 (Binary search) the picture seems to be wrong, since you first pick a string with minimum length, the string first picked should be leet rather than leets


  • 0

    Dear @lb71104208 ,
    Yes, there is a mistake in the image. I will update the article. Thank you for finding the problem.


  • 0

    @lb71104208 Thanks for pointing this out! I have published @elmirap 's revision, please refresh this page and take a look again.


  • 0
    T

    Don't know if I am missing anything. But for the followup, the question statement says "find the longest common substring among a string q and S"; however, the code seems to solve the question of common prefix instead of substring.


  • 0

    @tianyu This is probably a typo in the article. I will let @elmirap to confirm, thanks.


  • 0

    @1337c0d3r yes, this is a typo, will correct it. Thank you @tianyu


  • 0

    @tianyu Thanks, just fixed it.


  • 0
    S

    About the follow up, why do we need a trie? we can just compute the long common prefix of S_1, ..., S_n, say lcp_n and store it. Then for each query string q, just compute the lcp of q and lcp_n.


  • 0

    Because we expect to add new strings to the trie in the future which is O(n) - lenght of the string


  • 0
    S

    @elmirap said in Longest Common Prefix:

    to add new strings to the trie in the future which is O(n) - lenght of the string

    But whenever we add a new string S_n, we only need the LCP of S_1, S_2..., S_{n-1}. The LCP can't be longer, so we really don't care about the other info of S_1, S_2, ... S_{n-1} except for the LCP, right?


  • 0

    right, but the same way you add strings to trie, you can remove them, trie changes in time for example, you ask it queries for LCP


  • 0
    S

    Were you saying we also support removing some of the strings among S_1, ..., S_n? If that's the case, then using a trie to support removing strings do have an advantage. But the follow-up doesn't mention after deleting strings. Without the need of removing, I still don't see why a tire is necessary.


  • 0

    @stupidbird911 yes, exactly , you have a trie in which you can insert and delete and have a lot of LCP queries.


  • 0
    Y

    For Approach 1, isn't indexOf O(n), why the total time complexity is O(S)?


  • 0

    @yanwen4 For simplicity let's suggest that all strings has the same length m. In the worst case all strings will be equal and we call n times IndexOf. Algorithm is O( S) where S = n*m
    If strings are not equal , for example leet, lees,lest common prefix decrease by 1 each time call of IndexOf doesn't return 0. Since we compare only min (prefix, Si) characters ,total number of comparison is less than S


  • 0
    Y

    I don't think you just call n times indexOf, because you have a while-loop. Suppose all strings are equal, when you compare s1 and s2, if s2.indexOf(s1) != 0, you will reduce the length of s1 and call s2.indexOf(s1) again, and keep going. so I thought in worst case, the time complexity is O(n*m^2). Isn't it?


  • 0

    @yanwen4 no I don't think so


  • 0
    Y

    Hi @elmirap Thanks for your article. It is amazing. But I am still quite confused. What does links[ch -'a'] = node; do? Furthermore, How could you ensure that each character will link to others like the chart? I cannot see the code about it. Thanks!


  • 0

    @ynteng Each tree node had at most 26 links, one per each alphabet charcter. links[ch -'a'] = node assign next prefix character which is stored in node as a link to current prefix. For example if we have a and next charcter from the string is s.Character sis assigned as a children of the node which contains a, e.g links[ s -''a] = new node.
    On the second questino. Each node has at most 26 links, so some links wil be null


Log in to reply
 

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