My O(nk) solution TLE

  • 0

    use a Manacher algorithm O(nk) we can identify wether a substring within a word is a palindrome in O(1).
    Then we use a trie to save all word O(nk), then for each word x , we reverse it, and search it in the Trie character by character, at each time, we see if there is some word y and the rest part of x is palindrome.


  • 0

    That is possible. I did same thing before using python, and got TLE (I mentioned in my post). For this method, the worst case and best case is almost cost the same; but for some methods with higher time complexity, the best case / average case cost quite differently with worst case.

Log in to reply

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