string的变换
Given two words of equal length that are in a dictionary, write a method to transform
one word into another word by changing only one letter at a time. The new word you
get in each step must be in the dictionary.
EXAMPLE:
input: DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
请大侠们指点
谢谢
[解决办法]
1>将字典按1个字母单词、2个字母单词、3个……分类
2>对于每一类，设有k个元素，构造一个k*k的邻接矩阵，邻接条件就是两个单词只差一个字母，k*k/2的复杂度。
考虑到空间，由于是无向图，可以用半个矩阵存储，再节省一点就是用bit，每个bit代表一个关系。
这样如果原来是char型，现在用bit再加上半个矩阵，空间是原来的1/16.如果类里有10000个单词，那么用
10000*10000/16=6250000，约6M的存储空间，如果是100000个，就要600M，所以还要看词汇量。
由于那个矩阵大多是0，所以可能不是很划算，或许用链表更好一点。
3> 有了邻接矩阵后，就很好求路径了，基本所有算法书都有讲。
