A code in python3 need help for time efficiency

Question

I need to solve the problem below in python3 (within 3 sec).

• Problem definition:

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<=N,M<=1000). Next N lines contain exactly M characters.

Output: A single string

Sample input1:
1 9
arigatodl
Sample output1:
rigtodl

Sample input2:
5 6
cabboa
kiltik
rdetra
kelrek
dmcdnc
Sample output2:
codermn

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)

This is my code even it works, still not fast enough when N,M=1000. Any suggestion to improve the code faster would be helpful. Or any other ways to solve the given problem, as long as solution is in python3 and faster than mine.

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]