Python string comparison not working as intended?

Question

I'm currently working on a Codeforces problem (I'm not in a middle of a contest so it's not cheating!) and I can't get the string comparison part correctly for some reason.

The gist of the problem is that, given an array of strings, I have to calculate how many columns I have to remove to make the strings lexicographically in order. So for the second test case scenario, we're given

case
care
test
code

And the answer should be 2, with the first and third columns being removed and resulting in

ae
ae
et
oe

Attached below is my code:

#some code to take the input and convert it to a list s
begin = 0
out_list = [[] for i in range(n)]
while begin < m: #m is the length of each string
    out_copy = out_list[:]
    for i in range(n): #n is the number of strings
        out_copy[i].append(s[i][begin])
    fine = True
    for i in range(1,n):
        if ''.join(out_copy[i]) < ''.join(out_copy[i-1]):
            fine = False
    if fine:
        out_list = out_copy
    begin += 1
#some code to output the result

''.join(list) is supposed to give me a string that is a concatenation of all the characters in the list, and the < operator should be enough of a comparator for the computer to return False for the first column since c is less than t... but something must not be quite right here. What's going on?

@user2357112 - That's the only real way I knew how to copy the list... is there a better one? I'm open to suggestions! — 2012ssohn, Jun 11 '15 at 03:47
@2012ssohn See this as to how to copy a list http://stackoverflow.com/questions/2612802/how-to-clone-or-copy-a-list-in-python — Bhargav Rao, Jun 11 '15 at 03:48
@user2357112, that's a deep copy. See http://ideone.com/Y8qomw. — R Sahu, Jun 11 '15 at 04:10
With all due respect, gentlemen, could we discuss list copies on a different thread? — 2012ssohn, Jun 11 '15 at 04:14
@Alik - My question is about string comparisons, not about list copies. — 2012ssohn, Jun 11 '15 at 04:17
@2012ssohn you _think_ your problem is about string comparisons, but the problem is not about strings. Python compares strings correctly. _Your code_ copies list _incorrectly_ thus, `out_list` is being modified on each iteration regardless of `fine` flag — Konstantin, Jun 11 '15 at 04:19
@2012ssohn use `pdb` or just insert `print out_list` somewhere inside `while` loop — Konstantin, Jun 11 '15 at 04:21

score 1 · Answer 1 · answered Jun 11 '15 at 04:42

With this line

out_copy = out_list[:]

you make a shallow copy of out_list. Thus, out_list[i] and out_copy[i] refer to the same object.

Notice, that you mutate out_copy[i] on each iteration, so out_list[i] is changed on each iteration regardless of fine value. You can confirm it by adding print out_list inside the loop

begin = 0
out_list = [[] for i in range(n)]
while begin < m: #m is the length of each string
    print out_list
    out_copy = out_list[:]
    .....
    .....

outputs

[[], [], [], []]
[['c'], ['c'], ['t'], ['c']]
[['c', 'a'], ['c', 'a'], ['t', 'e'], ['c', 'o']]
[['c', 'a', 's'], ['c', 'a', 'r'], ['t', 'e', 's'], ['c', 'o', 'd']]

Make a deep copy instead.

import copy
begin = 0
out_list = [[] for i in range(n)]
while begin < m: #m is the length of each string
    out_copy = copy.deepcopy(out_list)
    .....
    .....
print out_list

produces correct result

[['a', 'e'], ['a', 'e'], ['e', 't'], ['o', 'e']]

Python string comparison not working as intended?

1 Answers1