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)?


  • 0

    @sschangi As explained earlier, adding a character to a string creates a new string. In the course of adding "a" + "b" + "c" + "d" incrementally, we've created intermediate strings "a", "ab", "abc", "abcd".


  • 0
    A

    Isn't using cur = cur.children.setdefault(char, TrieNode()) in the 3rd python solution quite inefficient, since you construct a new TrieNode even if you don't need it?


  • 0

    However, for the specific cases like if we use a StringBuilder for second solution in Java, the runtime can be optimized to O(K). As StringBuilder is essentially an ArrayList and the amortized runtime for insert is O(1)


  • 0

    However, for the specific cases like if we use a StringBuilder for second solution in Java, the runtime can be optimized to O(K). As StringBuilder is essentially an ArrayList and the amortized runtime for insert is O(1)


  • 0

    @amirshim In order to fully insert a key into the trie, we must have a node for every prefix of the key, making nodes if necessary.


Log in to reply
 

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