アルゴリズム雑記

前に面接問題に遭遇しましたが、2つの文字列(文字列は小文字のみで構成されている)が完全に同じ文字列であるかどうかを判断する.例えば文字列1:staff文字列2:fastfが条件を満たしている.当時『The-ART-Of-Programming-by-July』を見た中にはa,b,c,dの素数置換法が紹介されています.zを素数2,3,5,7に置き換える...2つの文字列の素数の積をそれぞれ求め、等しいかどうかを比較すればよい.

#!/usr/bin/env python
# -*- coding:utf-8 -*-

def get_res(string):
    bag = {
    'a':2,
    'b':3,
    ...
    'z':101
    }
    res = 1 
    for i in string:
        res = res * bag[i]
    return res

def same_char(str1, str2):
    res1 = get_res(str1)
    res2 = get_res(str2)
    return res1 == res2

当時は簡単に思いついたのですが、後で思い出してみればそれで済むのですが、乗積オーバーフローに直面しやすい状況で今日は『プログラミング珠玉』を見て、文字列1:staff対応署名をa 1 f 2 s 1 t 1文字列2対応署名をa 1 f 2 s 1 t 1と比較して判断できる署名法を紹介しました

#!/usr/bin/env python
# -*- coding:utf-8 -*-
def get_sign(string):
    bag={}
    for i in string:
        if i in bag.keys():
            bag[i] += 1
        else:
            bag[i] = 1
    res = ""
    for k in sorted(bag):
        res +='%s%s'%(k, bag[k])
    return res
def same_char(str1, str2):
    res1 = get_sign(str1)
    res2 = get_sign(str2)
    return res1 == res2

確かに良いアルゴリズムです
転載先:https://www.cnblogs.com/nixiaocang/p/6487203.html