算法题：多对字母merge

乱世小草

假设有很多对字母输入，字母的关系可以传递，有关系的字母合并成一组，例如：
a,b
c,d
a,d
x,y
x,z
合并结果：
a,b,c,d     
x,y,z
求时间复杂度最低的方法，谢谢！

gunjang

O(n2)可以的，用set或dict，如果字母对已存在，则更新，否则新建一个字母对
最后有几个set或dict就是几组
哦哦，没有考虑 ab cd，最后ac的情况，最后再来一轮合并就可以了

1. setlist=[]
   
2. def update(a,b):
   
3.         global setlist
   
4.         for aset in setlist:
   
5.                 if a in aset:
   
6.                         aset.add(b)
   
7.                         return
   
8.                 elif b in aset:
   
9.                         aset.add(a)
   
10.                         return
    
11.         aset = set([a,b])
    
12.         setlist.append(aset)
    
13. 
    
14. def merge():
    
15.         global setlist
    
16.         for i in range(len(setlist)-1, 0, -1):
    
17.                 for j in range(i):
    
18.                         if setlist[i] & setlist[j] != set([]):
    
19.                                 setlist[j] |= setlist[i]
    
20.                                 #remove i
    
21.                                 setlist.remove(setlist[i])
    
22.                                 break
    
23. 
    
24. update('a', 'b')
    
25. update('c', 'd')
    
26. update('a', 'd')
    
27. update('x', 'y')
    
28. update('x', 'z')
    
29. merge()
    
30. print(setlist) #[{'b', 'c', 'a', 'd'}, {'z', 'y', 'x'}]

复制代码

随便写的

SixPy

1. s ='''
   
2. a,b
   
3. c,d
   
4. a,d
   
5. x,y
   
6. x,z
   
7. '''
   
8. ls = [set(x.split(','))for x in s.split()]
   
9. rslt = []
   
10. while ls:
    
11.     st = ls.pop()
    
12.     for i in range(len(ls)):
    
13.         if st & ls[i]:
    
14.             ls[i] |= st
    
15.             break
    
16.     else:
    
17.         rslt.append(st)
    
18. 
    
19. print(rslt)
    

复制代码