Map Sum


  • 0

    Click here to see the full article post


  • 0

    I'm sorry, but why is "Every insert operation is O(K^2)" ?
    Isn't it K? It's just iterating one character at a time, and prefix += c is O(1).


  • 0
    J

    @wavy
    prefix += c is O(1)
    No it isn't - Java string is immutable. On each concatenation a new string is created, copying character by character and then appending the new character c. Each concatenation is O(K) on average.

    Edit: Same for the python example. I guess if the string is mutable (like in Ruby using << operator) then the time complexity should be O(K)


  • 0
    K

    The Java code you provided in approach 3 has a class called TrieNode, which has an attribute "end" but I don't see any usage of it in your code. Why did you add it?


  • 0

    @jwgoh said in Map Sum:

    No it isn't - Java string is immutable. On each concatenation a new string is created, copying character by character and then appending the new character c. Each concatenation is O(K) on average.

    Thanks for let me know. I think you are right, and we need to have test case for string length above 10000 to give TLE


  • 0

    @kk636 It has been corrected. Thank you


  • 0
    K

    @awice Sorry. I don't see any change to the code.


  • 0

    Nice explanation. Thank you!


  • 0
    S

    I have the same confusion as raised before: why in approach 2, insert operation is O(K^2)? Isn't it O(K)?


Log in to reply
 

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