Click here to see the full article post
Similar advice holds for Python. Instead of concatenation in a loop, form a list of strings and then use "".join(string_list) after the loop has completed.
I also can't understand why String operate is O(n^2), would someone like explaining it?
@xiaowu4 Strings concatenation operates in O(n) but in the case above they were talking about it being O(n^2) because it was concatenating inside the for loop which is already O(n).
In python + is faster than ''.join() and there is nothing called append().
%timeit "a"*10 + "b"*10
The slowest run took 6.07 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 224 ns per loop
%timeit ''.join(['a'*10, 'b'*10])
The slowest run took 9.30 times longer than the fastest. This could mean that an intermediate result is being cached.
1000000 loops, best of 3: 369 ns per loop
@poo-sesha-gmail-com You should test concatenating n strings, not just two. And the Python equivalent is to collect the parts in a
list, which does have
@FiftyShades , this is because you had the variable S but created an array to hold a number of characters (s.Length)
@Artix Let me answer my own question:
For python, we can use a list(mutable data type) to represent the whole string.
Append one 'hello' each time.
At last, use ''.join to forge the whole string.
li= s = ''; for i in range(n): li.append('hello')'; s = ''.join(li)
This runtime should be O(n).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.