Space complexity of list creation
<p>Could someone explain me what is the space complexity of beyond program, and why is it?</p>

<pre><code>def is_pal_per(str):

s = [i for i in str]
nums = [0] * 129

for i in s:
    nums[ord(i)] += 1

count = 0

for i in nums:
    if i != 0 and i / 2 == 0:
        count += 1

print count

if count &gt; 1:
    return False
else:
    return True
</code></pre>

<p>Actually, i'm interested in this lines of code. How does it influence on space complexity of above program?</p>

<pre><code>s = [i for i in str]
</code></pre>

<p><code>nums = [0] * 129</code></p>

<p>I'm unclear where you're having trouble with this.  <strong>s</strong> is simply a list of individual characters in <strong>str</strong>.  The space consumption is <strong>len(s)</strong>.</p>

<p><strong>nums</strong> is a constant size, dominated by the <strong>O(N)</strong> term.</p>

<p>Is this code you wrote, or has this been handed to you?  The programming style is highly <em>not</em> "Pythonic".</p>

<hr>

<p>As for your code, start with this collapse:</p>

<pre><code>count = 0

for char in str:
    val = ord[char] + 1
    if abs(val) == 1:
        count += 1

print count

return count == 0
</code></pre>

<p>First, I replaced your single-letter variables (<strong>s</strong> => <strong>char</strong>; <strong>i</strong> => <strong>val</strong>).  Then I cut out <em>most</em> of the intermediate steps, leaving in a couple to help you read the code.  Finally, I used a straightforward Boolean value to return, rather than the convoluted statement of the original.</p>

<p>I did <em>not</em> use Python's counting methods -- that would shorten the function even more.  By the way, do you <em>have</em> to print the count of unity values, or do you just need the Boolean return?  If it's just the return value, you can make this even shorter.</p>

python algorithm python-2.7 space-complexity