Printing characters in a matrix as a string

Question

I need to solve this problem in Python 3 (within 3 sec):

A is a given (NxM) rectangle, filled with characters "a" to "z". Start from A[1][1] to A[N][M] collect all character which is only one in its row and column, print them as a string.

Input:

\$N\,ドル \$M\$ in first line (number of row and column \1ドル \le N\,ドル \$M \le > 1000\$). Next, \$N\$ lines contain exactly \$M\$ characters.

Output:

A single string

Sample input 1:

1 9
arigatodl

Sample output 1:

rigtodl

Sample input 2:

5 6
cabboa
kiltik
rdetra
kelrek
dmcdnc

Sample output 2:

codermn

This is still not fast enough when \$N\,ドル \$M\$ = 1000. I'd like suggestions on improving the speed, or any other ways to solve the given problem, as long as the solution is in Python 3 and is faster than mine.

from operator import itemgetter
Words,Chars,answer=[],"abcdefghijklmnopqrstuvwxyz",""
N,M=[int(i) for i in input().split()]
for _ in range(N):
 Words.append(input())
 # got the inputs
for row,word in enumerate(Words): # going through each words
 Doubts=[] # collect chars only one in its row.
 for char in Chars:
 if (word.count(char)==1):
 Doubts.append((char,word.index(char)))
 for case in sorted(Doubts,key=itemgetter(1)): #sorting by index
 doubtless=True #checking whether 1 in its column or not.
 for i in range(N):
 if (Words[i][case[1]]==case[0] and i!=row):
 doubtless=False
 break
 if (doubtless):
 answer+=case[0] #if char is one in its row and column, adds to answer.
print (answer)

• Joel Cornett: Not an observation about optimization, but why aren't you using PEP8 guidelines to write your code? It's not a dealbreaker by any means, but 1) Why don't you have spaces between operators and 2) Capital/CamelCase is usually reserved for class definitions.
• Naagii: Thanks, but this time I wasn't wondering about how it looks. I was worrying about how it works :)
• halfer: For info, this has been cross-posted at StackOverflow.
• halfer: You didn't have to delete it, just declare the cross-posting. Then people can use the hyperlink to determine whether you still need assistance. It's about being considerate of other people's time, and as I said on the other thread, this has been part of netiquette for thirty years or so.
• Joel Cornett: I'll take a look at it a bit more in depth, but it appears that you're iterating over the elements in the matrix more times then necessary. You should be able to write an algorithm that does at most N * M * k_nm checks, where k is the number of unique letters in each row/column. (by unique I mean a member of the set of letters, I don't mean that they don't repeat in the sequence)

Answer 1

I would suggest to create a 1000x1000 testcase and measure the performance before the optimization process. Please use the following test generator:

import os
import random
f = open('1000x1000.in','w')
f.write('1000 1000\n')
ALPHABET = 'abcdefghijklmnopqrstuvwxyz'
for _ in range(1000):
 f.write(''.join([ALPHABET[random.randint(0, len(ALPHABET)-1)] for _ in range(1000)]) + '\n')
f.close()

After that just run it and measure the performance of your application. I got about 47 ms on my pretty old C2D E7200.

Answer 2

You could improve part of your loop.

Doubts=[] 
for char in Chars:
 if (word.count(char)==1):
 Doubts.append((char,word.index(char)))

Can be done with list-comprehension.

 Doubts = [(char, word.index(char)) for char in Chars if word.count(char) == 1]