欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

“变位词”判断问题及算法复杂度

程序员文章站 2023-11-13 14:20:58
解法1 逐字检查解法思路:将词1中的字符逐个到词2中检查是否存在,存在就打勾标记(防止重复检查)。如果每个字符都能找到,则两个词是变位词。只要有一个字符找不到,就不是变位词。实现打勾标记:将词2对应字符设为None,由于字符串是不可变类型,需要先复制到列表中。......

“变位词”判断问题及算法复杂度

解法1 逐字检查

解法思路:

将词1中的字符逐个到词2中检查是否存在,存在就打勾标记(防止重复检查)。如果每个字符都能找到,则两个词是变位词。只要有一个字符找不到,就不是变位词。
“变位词”判断问题及算法复杂度
实现打勾标记:将词2对应字符设为None,由于字符串是不可变类型,需要先复制到列表中。

#判断两个词是否为变位词
def anagramSolution(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:#对s2逐个对比
            if s1[pos1]==alist[pos2]:
                found=True
            else:
                pos2=pos2+1
        if found:
            alist[pos2]=None#若找到将其变为None
        else:
            stillOK=False#未找到失败
        pos1=pos1+1
    return stillOK
                    
print(anagramSolution('abcd','dcba'))
print(anagramSolution('python','cython'))    

时间复杂度分析

“变位词”判断问题及算法复杂度

解法2 排序比较

解法思路:

将两个字符串都按照字母顺序排好序,再逐个字符对比是否相同,如果相同则是变位词,有任何不同就不是变位词。
“变位词”判断问题及算法复杂度

#解法2 :判断两个词是否为变位词
def anagramSolution(s1,s2):
    alist1=list(s1)
    alist2=list(s2)
    alist1.sort()
    alist2.sort()
    pos=0
    stillOK=True
    while pos<len(s1) and stillOK:
        if alist1[pos]==alist2[pos]:
            pos=pos+1
        else:
            stillOK=False
    return stillOK
print(anagramSolution('abcd','dcba'))
print(anagramSolution('python','cython')) 

时间复杂度分析

“变位词”判断问题及算法复杂度

解法3 计数比较

解法思路:

对比两个词中每个字母出现的次数,如果26个字母出现的次数都相同,这两个字符串一定为变位词。

具体做法:

为每个词设置一个26位的计数器,先检查每个词,在计算其中设定好每个自出出现的次数。计数完成后,进入比较阶段,看两个字符串的计数器是否相同,如果相同则是变位词。

#解法3 计数比较
def anagramSolution(s1,s2):
    counter1=[0]*26
    counter2=[0]*26
    #对字符串s1和s2分别计数
    for i in range(len(s1)):
        pos1=ord(s1[i])-ord('a')
        counter1[pos1]=counter1[pos1]+1#ord()返回字符对应的ASCII码值
    for j in range(len(s2)):
        pos2=ord(s2[j])-ord('a')
        counter2[pos2]=counter2[pos2]+1#ord()返回字符对应的ASCII码值
    stillOK=True
    pos=0
    #对两个计数器内容进行比较
    while pos<26 and stillOK:
        if counter1[pos]==counter2[pos]:
            pos=pos+1
        else:
            stillOK=False
    return stillOK
print(anagramSolution('abcd','dcba'))
print(anagramSolution('python','cython')) 

时间复杂度分析“变位词”判断问题及算法复杂度

“变位词”判断问题及算法复杂度

本文地址:https://blog.csdn.net/weixin_38324954/article/details/107059938