高效变位词查找

       变位词指的是一个单词经过改编字母顺序之后得到的另一个单词。在变位过程中不可以移除任何字母。

        在一个数组或集合中查找指定字符串的变位词,最简单粗暴的方式就是遍历数组中的元素,每一次对比字符串两个字符串的元素是否相同。这样做是可以实现但效率非常低。对于长度为m的列表,且单词平均长度为n,算法对每个单词需要扫描n次,每次检查一个字母。算法的复杂度为O(m*n!),n越大复杂度会呈几何倍的增长。

         简单的算法就是根据单词签名来判断。

         将单词的所有字母按照字母顺序排序得到的字母序列就是这个每一个单词的签名,每个单词都可以有一个算法签名,给定单词的所有变位词都会有一个相同的签名

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容