变位词判断-python

谁践踏了优雅 2023-07-09 02:28 10阅读 0赞

> 《Python数据结构与算法分析》（第二版）

写一个bool函数，以两个词为参数，返回这两个词是否为变位词。（假设参与判断的两个词仅由小写字母组成，且长度相等如：abcd和cdab)

# !/user/bin/env python
    # coding:utf-8
    
    #方案1：清点法(时间复杂度为平方）
    def anagramSolution1(s1, s2):
        alist = list(s2)#把s2复制到列表中，以便查找时做修改
        pos1 = 0
        stillOK = True
        while pos1 < len(s1) and stillOK:#逐个取出s1中字母
            pos2 = 0
            fit = False
            while pos2 < len(alist) and not fit:#与s2进行逐个对比
                if s1[pos1] == alist[pos2]:
                    fit = True#找到
                else:
                    pos2 = pos2 + 1#未找到，继续与下一个对比
            if fit:
                alist[pos2] = None#若找到，则消去该位上的字母
            else:
                stillOK = False#若未找到，程序终止
            pos1 = pos1 + 1
        return stillOK
    
    
    str1 = str(input('please input the first word: '))
    str2 = str(input('please input the second word: '))
    if anagramSolution1(str1, str2):
        print('anagram')
    else:
        print('not anagram')
    
    
    #方案2：排序法(时间复杂度取决于排序算法)
    def anagramSolution2(s1, s2):
        alist1 = list(s1)
        alist2 = list(s2)
    
        alist1.sort()#若为变位词，则排序后得到相同的字符串
        alist2.sort()
    
        pos = 0
        matches = True
        while pos < len(alist1) and matches:
            if alist1[pos] == alist2[pos]:
                pos = pos +1
            else:
                matches = False
        return match
    
    
    str1 = str(input('please enter the first string: '))
    str2 = str(input('please enter the second string: '))
    
    print('anagram is %s' % anagramSolution2(str1, str2))
    
    
    #计数法(以空间换取时间，时间复杂度为线性)
    def anagramSolution3(s1, s2):
        c1 = [0] * 26#字符可能有26种情况，所以使用26个计数器，若两个计数器列表相同，那么这两个词肯定为变序词
        c2 = [0] * 26
    
        for i in range(len(s1)):
            pos = ord(s1[i]) - ord('a') #ord()函数返回字符对应的ASCII数值
            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