Apache Pivot教程 TensorRT WorldCloud 海思 tsql notifications vue使用教程 vue的钩子函数 oracle查看数据库 js数组截取前5个 图片生成链接 查看mysql密码 oracle数据库创建表空间 python例子 java抽象类 java入门级教程 java类型 java得到当前时间 java中map java如何编写接口 javascript实例 千千静听绿色版 内存修改器 神龙激活 din字体 0x8002801c php抓取网页数据 选择模拟位置信息应用 坐标标注插件 视频编辑专家下载 js文件上传 js验证码 hyqihei 证书小精灵 编程电子书 windows游戏编程 欧洲卡车模拟2存档 vc运行库合集 预测未来长相的软件 php上传文件
当前位置: 首页 > 学习教程  > python

“变位词”判断问题的几种解法——数据结构与算法Python练习(1)

2021/2/7 9:55:06 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

所谓“变位词”是指两个词之间存在组成字母的重新排列关系 如:heart和earth,python和typhon 为了简单起见,假设参与判断的两个词仅由小写字母构成,而且长度相等。 解法1:逐字检查-程序代码 解法思路 将词1中的字符逐个…

所谓“变位词”是指两个词之间存在组成字母的重新排列关系
如:heartearthpythontyphon
为了简单起见,假设参与判断的两个词仅由小写字母构成,而且长度相等。

解法1:逐字检查-程序代码
解法思路
将词1中的字符逐个到词2中检查是否存在
存在就“打勾”标记(防止重复检查)
如果每个字符都能找到,则两个词是变位词
只要有1个字符找不到,就不是变位词

# encoding:utf-8
def anagramSolution1(s1, s2):   #传入两个字符串参数
    alist = list(s2)    #由于字符串是不可变类型,需要先复制到列表中
    pos1 = 0            #当前索引初始化
    stillOK = True      #定义匹配标志
    while pos1 < len(s1) and stillOK:  #循环s1的每个字符
        pos2 = 0
        found = False   #定义不匹配标志
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True    #在s2逐个对比
            else:
                pos2 = pos2+1
        if found:
            alist[pos2] = None  #找到,打勾
        else:
            stillOK = False
        pos1 = pos1 + 1
    return stillOK     #未找到,失败

print(anagramSolution1('abcd','abcd'))

Debug调试:
两个变位词逐个元素对比,如果能在另一个中找到就打钩(设为NONE).
在这里插入图片描述
解法2:排序比较
将两个字符串都按照字母顺序排好序再逐个字符对比是否相同,如果相同则是变位词,有任何不同就不是变位词。

个人认为这一种解法在原理和算法实现上都是逻辑最清晰易懂的。

# encoding:utf-8
def anagramSolution2(s1, s2) :
    alist1 = list(s1)
    alist2 = list(s2)
    alist1.sort()
    alist2.sort()
    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if alist1[pos] == alist2 [pos] :
            pos=pos+1
        else:
            matches = False
    return matches

print(anagramSolution2 ('abcde' , 'decba'))

注:排序过程也要先消耗一定时间去执行,粗看上去,本算法只有一个循环,最多执行n次,数量级是O(n),但循环前面的两个sort并不是无代价的;
排序算法采用不同的解决方案,其运行时间数量级差不多是O(n2)或者O(n log n).

解法3.暴力法
暴力法解题思路为:穷尽所有可能组合,
将s1中出现的字符进行全排列(n个字符进行全排列,其所有可能的字符串个数为n!),再查看s2是否出现在全排列列表中。
在这里插入图片描述

#encoding:utf-8
def permutation(li,l2):
  len_list = len(li)
  if len_list == 1:
    return li

  result = []
  for i in range(len_list):
    res_list = li[:i] + li[i+1:]
    s = li[i]
    per_result = permutation(res_list,l2)
    if len(per_result) == 1:
      result.append(li[i:i + 1] + per_result)
    else:
      result += [[s] + j for j in per_result]
  for j in range(len(result)):
      if result[j] == l2:
          print("True")
      else:
          pass
  return result

print(permutation(list("abcd"),list("bcad")))

运行结果:

True
[[‘a’, ‘b’, ‘c’, ‘d’], [‘a’, ‘b’, ‘d’, ‘c’], [‘a’, ‘c’, ‘b’, ‘d’], [‘a’, ‘c’, ‘d’, ‘b’], [‘a’, ‘d’, ‘b’, ‘c’], [‘a’, ‘d’, ‘c’, ‘b’], [‘b’, ‘a’, ‘c’, ‘d’], [‘b’, ‘a’, ‘d’, ‘c’], [‘b’, ‘c’, ‘a’, ‘d’], [‘b’, ‘c’, ‘d’, ‘a’], [‘b’, ‘d’, ‘a’, ‘c’], [‘b’, ‘d’, ‘c’, ‘a’], [‘c’, ‘a’, ‘b’, ‘d’], [‘c’, ‘a’, ‘d’, ‘b’], [‘c’, ‘b’, ‘a’, ‘d’], [‘c’, ‘b’, ‘d’, ‘a’], [‘c’, ‘d’, ‘a’, ‘b’], [‘c’, ‘d’, ‘b’, ‘a’], [‘d’, ‘a’, ‘b’, ‘c’], [‘d’, ‘a’, ‘c’, ‘b’], [‘d’, ‘b’, ‘a’, ‘c’], [‘d’, ‘b’, ‘c’, ‘a’], [‘d’, ‘c’, ‘a’, ‘b’], [‘d’, ‘c’, ‘b’, ‘a’]]

解法4:计数比较
解题思路:对比两个词中每个字母出现的次数,如果26个字母出现的次数都相同的 话,这两个字符串就一定是变位词。
具体做法:为每个词设置一个26位的计数器,先检查每个词,在计数器中设定好每个字母出现的次数;
计数完成后,进入比较阶段,看两个字符串的计数器是否相同,如果相同则输出是变位词的结论。

#encoding:utf-8
def anagramSolution4(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1
    j = 0
    stillOK = True
    while j < 26 and stillOK:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            stillOK = False
    return stillOK

print(anagramSolution4('apple', 'pleap'))

计数比较算法中有3个循环迭代,但不像解法1那样存在嵌套循坏
前两个循环用于对字符串进行计数,操作次数等于字符串长度n 第3个循环用于计数器比较,操作次数总是26次 ;
所以总操作次数T(n)=2n+26,其数量级为O(n),这是一个线性数量级的算法,是4个变位词判断算法中性能最优的。


本文链接: http://www.dtmao.cc/news_show_2000195.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?