图的邻接表和邻接矩阵表示最为常用，但是有时需要建图时这两种表示效率不是很高，因为需要构造每个结点和每一条边。此时使用一些隐式的表示方法可以提升建图效率。
classSolution:
defladderLength(self, beginWord: str, endWord: str, wordList: List[str]) ->int:
N, K=len(wordList), len(beginWord)
find_end=Falseforiinrange(N):
ifwordList[i] ==endWord:
find_end=Truebreakifnotfind_end:
return0wordList.append(beginWord)
N+=1# clustering nodes for efficiency compare to adjacent listcluster=collections.defaultdict(list)
foriinrange(N):
node=wordList[i]
forjinrange(K):
cluster[node[:j] +'*'+node[j+1:]].append(node)
# bidirectional BFSvisited_start, visited_end=set([beginWord]), set([endWord])
bfs_start, bfs_end=collections.deque([beginWord]), collections.deque([endWord])
step=2whilebfs_startandbfs_end:
# startnum_level=len(bfs_start)
whilenum_level>0:
node=bfs_start.popleft()
forjinrange(K):
key=node[:j] +'*'+node[j+1:]
fornincluster[key]:
ifninvisited_end:
returnstep*2-2ifnnotinvisited_start:
visited_start.add(n)
bfs_start.append(n)
num_level-=1# endnum_level=len(bfs_end)
whilenum_level>0:
node=bfs_end.popleft()
forjinrange(K):
key=node[:j] +'*'+node[j+1:]
fornincluster[key]:
ifninvisited_start:
returnstep*2-1ifnnotinvisited_end:
visited_end.add(n)
bfs_end.append(n)
num_level-=1step+=1return0