算法的最大单词形成perodic表元素
我想为以下问题场景编写一个算法
以周期表元素的名称，找到可以形成的最大的词？ Na ， Ne等符号应视为单一元素。
这在一家知名公司的求职面试中被问到。 任何人都可以帮我解决这个问题。
如何将一个给定的单词表达为化合物？ 这是一个动态编程解决方案。 重要的一行是“让进展[i]成为词[：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镜BrONCHoEsOPHAgOsCoPY HYPErPHOsPHoReSCeNCe HYPSiBrAcHYCePHAlISm 我认为更好的方法是检查字典中的每个单词，看看它是否可以由元素的名称组成。 检查元素的每个排列都会更难编程，效率会更低。
虽然我同意制作这些组合的过程比较容易，但是其中的太多方法是正确的，正如你所说的，如果你没有给出限制，它往往是无穷的。 带有符号的单词的制作会稍微困难一些，但我认为这不会太困难。
例如，当你得到一个单词时，你可以搜索元素来寻找可以组成你的单词的元素，然后使用这组元素尝试并从头到尾填入字母。 显然，对于不是2个字母和长度奇数的单词的元素会变得更加困难。
你实际上可以使用一种图形。 假设你有'硅'。 您可以从表中的字母'S'或'SI'开始。 从那里选择'SI'是因为它更接近您的解决方案。 如果'SI'不能导致你的解决方案，你将不得不回头看看'S'是否会起作用。
所以它可以作为一种深度优先搜索。
生成所有单词并检查它们是否存在是不切实际的。 长度为L的文字有118 ^ L个，生长功能太快。 1,643,032三个符号词！
正如Makoto所建议的，相反，效率更高。 尝试重建字典中的每个单词。 大约有25万英语单词。
检查单词很简单：查看是否有任何元素符号与单词的开头匹配，然后继续使用其余字符。
你必须尝试所有可能的比赛，因为比赛可能会隐藏另一场比赛 （我的意思是字ABC可以用符号A匹配，然后被卡住，因为BC不可用，但它可能是AB和C）。所以匹配函数将是递归的。 我不希望在这个匹配过程中发生指数爆炸。
为了最大限度地提高效率，您可以将符号存储在http://ter.wikipedia.org/wiki/Trie的trie结构中。
最后的提示：因为你只是被要求找到最长的比赛，所以通过减少长度来试试这些单词，并在第一场比赛中停下来。
这是一个简单的Python解决方案，没有任何优化。 匹配是从右到左进行的，以允许在后序中打印符号序列：
Words= ['K', 'NaH', 'NaNaNaNa', 'HaKuNa']
Symbols= ['Na','K','H']
def Match(Word):
# Match the end of the word with every symbol
for S in Symbols:
# In case of a partial match, recurse on the prefix
if S == Word or (S == Word[-len(S):] and Match(Word[:-len(S)])):
print S,
return True
# No match, report failure
return False
for W in Words:
if Match(W):
print
>>>
K
Na H
Na Na Na Na
上一篇: Algorithm for largest word formed from perodic table elements
下一篇: Can localStorage slow down my website when used frequently?