从perodic table元素形成的最大单词的算法

Question

我想为以下问题场景编写算法

获取周期表元素的名称,找到可以形成的最大单词？如符号Na, Ne等应被视为单个元件.

这是在一家知名公司的求职面试中被问到的.任何人都可以帮我解决这个问题.

Answer 1

如何将给定单词表示为化合物？这是一个动态规划解决方案。重要的一行是“让progress[i]成为word[:i]子问题的解”。其余的如下。

elements = "H He Li Be B C N O F Ne Na Mg Al Si P S Cl Ar K Ca Sc Ti V Cr Mn Fe Co Ni Cu Zn Ga Ge As Se Br Kr Rb Sr Y Zr Nb Mo Tc Ru Rh Pd Ag Cd In Sn Sb Te I Xe Cs Ba La Ce Pr Nd Pm Sm Eu Gd Tb Dy Ho Er Tm Yb Lu Hf Ta W Re Os Ir Pt Au Hg Tl Pb Bi Po At Rn Fr Ra Ac Th Pa U Np Pu Am Cm Bk Cf Es Fm Md No Lr Rf Db Sg Bh Hs Mt Ds Rg Cn Uut Fl Uup Lv Uus Uuo".split()

def decompose(word):
    """Express given word as chemical compound. If there are multiple solutions, return one of minimal weight."""
    progress = [False for x in range(len(word)+1)] # solution for word[:i]
    progress[0] = []

    for i in range(1, len(word)+1):
        possibles = list()
        for j in range(max(i-3,0), i):
            if progress[j] == False:
                continue
            alchemical = word[j:i].title()
            if alchemical in elements:
                possibles.append(progress[j] + [alchemical])

        if possibles:
            # choose minimal solution
            progress[i] = min(possibles, key=len)

    if progress[-1] == False:
        return False
    return "".join(progress[-1])

assert decompose("sine") == "SiNe" # rather than S-I-Ne
assert decompose("bismuth") == "BiSmUTh"
assert decompose("jam") == False

https://gist.github.com/hickford/750135db633832913703

在整个字典上运行这个，最长的复合词是：

• 非表征主义NoNRePReSeNTaTiONaLiSm
• 热磷光ThErMoPHOsPHoReSCeNCe
• 支气管食管镜检查BrONCHoEsOPHAgOsCoPY
• 超磷光HYPErPHOsPHoReSCeNCe
• 上短头畸形HYPSiBrAcHYCePHAlISm