AtCoder Beginner Contest 302 C-Almost Equalの解答

atcoder.jp

・考え方：N,Mが小さいので全部の順列を試して、隣り合う文字列の文字のうち1つだけ違う文字があればcnt+=1として、文字が1つだけ違う、つまりcnt=1のときfcnt+=1と加算する。これを全部の隣り合う文字列に対してやり、fcnt=N-1、つまり隣り合う全ての文字列が1文字違いのときprint("Yes")でプログラム終了、そうでないときNoを出力。

・実装例

import itertools

N,M=map(int,input().split())
S=[]
for _ in range(N):
  S.append(input())


for p in itertools.permutations(S,N):
  fcnt=0
  for i in range(N-1):
    cnt=0
    for j in range(M):
      #print(p[i][j])   #例えばp=(abcd,efgh)のとき, p[0]=abcd, p[0][0]=aとなる。
      if p[i][j]!=p[i+1][j]:
        cnt+=1
    if cnt==1:
      fcnt+=1
  if fcnt==N-1:
    print("Yes")
    exit()
print("No")