首先膜拜32MS的大牛...

我只会DP+剪枝 - -

思路:
1.将每个单词字典序 acb -> abc
2.按单词长度排序，长度相同的按字典序排
    acb ab aab
  ->ab aab acb
3.剪枝一: 如果words[i]与words[i-1]相同，删掉words[i]
4.DP
  4.1 剪枝二: 如果words[i]和words[i-1]长度之差 > 1， 不必搜索words[i]之前的单词了，必然words[i]不会是前面任何单词的extention
  4.2 剪枝三: 如果words[i]和words[i-1]长度之差 > 1， 且从words[i]到最后一个单词不同长度的种类数小于已经找到的最大长度，DP结束

没有剪枝一和二的时候超时了，剪枝三对于该题的测试数据而言没啥用。 


2004	Accepted	708K	813MS	C++	3013B	2012-05-14 23:26:11

• Re:一些剪枝 (37) CodingDream 2012-05-14 23:42:06