codefight上第33题，给一个字符串列表，如果两个字符串相差1个字母，判定可以连接。要求判定整个列表是否可以连接起来，直接使用暴力算法，用迭代器permuations方法，列出所有可能的排列，然后判定能否从头串到尾。
写完了才想起来是个汉密尔顿路径问题，应该有些更好的方法。由于是个NP完全问题，所以速度提高空间非常有限。
# This is a hamilertion path problem.
# First create a matrix to save possible path for each point by funtion "issm"
import copy
def solution(a):
matrix=[]
b=copy.copy(a)
print("len(a)",len(a))
if len(a)==2:
if issm(a[0],a[1])==1:
return True
else:
return False
elif len(a)==1:
return True
for i in range(len(a)):#构建矩阵
n=[]
for j in range(len(a)):
n.append(issm(a[i],a[j]))
print("n:",n)
matrix.append(n)
print("matrix，",matrix)
# 逐一计算每行，判定是否存在接口，同时有完全相同元素的元素，返回False。此类情况，说明2个相同元素链接到同一个第三元素上，拓扑上是分支结构。
m=[]#接口数
n=[]#完全一样的字符串数
for i in range(len(matrix)):
if matrix[i].count(1)==0 or (matrix[i].count(1)==1 and matrix[i].count(0)>1 and len(a)>3):
return False
m.append(matrix[i].count(1))
n.append(matrix[i].count(0))
print("m:",m)
print("n:",n)
print("old a",a)
if m.count(1)>2:
return False
else:
for i in range(len(a)):
if matrix[i].count(1)==1:
a.remove(b[i])
if len(a)==len(b):
a.pop()
print("new a",a)
return(solution(a))
def issm(b,c): #计算相似性，返回2个字段差异
n=0
for i in range(len(b)):
if b[i]!=c[i]:
n=n+1
else:
n=n+0
if n==1:
return(1)
else:
return(0)
