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 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]==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)
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.