I need to solve this problem in Python 3 (within 3 sec):
Ais a given (NxM) rectangle, filled with characters "a" to "z". Start from
A[N][M]collect all character which is only one in its row and column, print them as a string.
\$N\$, \$M\$ in first line (number of row and column \$1 \le N\$, \$M \le > 1000\$). Next, \$N\$ lines contain exactly \$M\$ characters.
A single string
Sample input 1:
1 9 arigatodl
Sample output 1:
Sample input 2:
5 6 cabboa kiltik rdetra kelrek dmcdnc
Sample output 2:
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]==case and i!=row): doubtless=False break if (doubtless): answer+=case #if char is one in its row and column, adds to answer. print (answer)