元素周期表中最长单词的算法

Question

元素周期表中最长单词的算法

algorithmcpu-word

7

我希望为以下问题情境编写算法：

给定元素周期表中的元素名称，找到可以组成的最长单词？

需要将像Na，Ne这样的符号视为单个元素。

这是在一家知名公司的面试中提出的问题。请问有谁能帮我解决这个问题？

- Ritesh

有无限的单词，没有字典怎么比较呢？ - coder hacker

1

I.N.C.O.N.S.P.I.C.U.O.U.S.N.Es.S - Egor Skriptunoff

2

如果你想找到最长的单词，第一步应该是将字典按照从长到短的顺序排序。然后从顶部开始尝试，找到可以用元素周期表中的符号构建的第一个单词。 - Shahbaz

1

@Shahbaz，仅通过长度对字典进行排序并在第一个匹配项处停止并不一定会给出正确的答案，因为多字母元素仅计为一个符号。也许问题的意图是想看看你是否试图聪明地优化代码中的错误。 - Daniel Brückner

1

“找到可以组成的最大单词”实际上是有歧义的。他们需要最大的元素组合，还是最大的结果单词？ - Shahbaz

显示剩余3条评论

7个回答

1

生成所有单词并检查它们是否存在是不切实际的。长度为 L 的单词有 118^L 个，这是一个增长速度太快的函数。有 1,643,032 个三个符号的单词！

另一种方法是像 Makoto 建议的那样更有效率。尝试从字典中重建每个单词。英语单词大约有 250,000 个。

检查一个单词很简单：看看任何元素符号是否与单词的开头匹配，并继续处理剩余字符。

您必须尝试所有可能的匹配，因为一个匹配可能会隐藏另一个匹配。（我的意思是单词 ABC 可能被符号 A 匹配然后卡住，因为 BC 不可用，但是 AB 和 C 可以匹配。）因此，匹配函数将是递归的。我不希望在这个匹配过程中出现指数级的爆炸。

为了最大效率，您将使用 trie 结构http://en.wikipedia.org/wiki/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

- user1196549

对字典进行排序并在第一个匹配项处停止可能会给出错误的答案，因为多个字母的元素仅计算为一个符号。 - Daniel Brückner

@Daniel：没错。可以通过继续搜索直到找到长度与最长单词符号数相等的单词来解决这个问题。 - user1196549

@Niklas：DP 怎么能帮助这里？ - user1196549

如果你只是对“Match”进行备忘录优化，那么你已经成功了，因为它只会使用 O(n*m) 种不同的输入调用，其中 n 是单词数，m 是最大单词长度。 - Niklas B.

@Niklas：你认为记忆化搜索算法是动态规划吗？ - user1196549

显示剩余2条评论

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

- Colonel Panic

0

我只是想记录下我的想法，并与其他专业的算法人员进行验证，因为我在其他地方没有看到这样的问题。

顺便说一句，我使用Java。以下是我的伪代码：

1、使用元素周期表符号来形成一个字符串数组：String[] PeriTable。

2、基于回溯思想，构建一个名为Backtracking(String result, String[] PeriTable, String[] used)的辅助函数；

3、我们遍历PeriTable中的每个元素，并检查它所形成的字符串。

 Backtracking void(String result, String[] PeriTable, String[] used){
   for(int i=0;i<PeriTable.length;i++){
     If(!used.contain(PeriTable[i])){
      newResult=result+PeriTable[i];
     If(isEnglishWord(newResult)) {
         used.add(PeriTable[i]);
         maxlength=Math.max(maxlength,newResult.length());
         Backtracking(newResult, PeriTable, used);
         used.remove(used.length()-1);
      }
    }
    else continue;
  }
 }

然而，我不知道如何构建isEnglishWord(); 函数。

- Chimo Jiang

0

生成所有可能的单词 - 幼稚的方法。

基于生成所有长度的排列：

import itertools..
symbols = ['Na','K','H']
for i in range(len(symbols)):
 for word in itertools.permutations(symbols,i+1):
  print( ''.join(word) )

您可以生成每种可能的组合，并检查它是否是实际单词。但这是低效的，仅适用于不允许符号重复的情况。

检查单词是否可以由符号构建 - 仍然不完美。

如果允许重复，则需要将单词与符号列表进行比较。我建议采用以下方法：

import itertools..
words = ['K', 'NaH', 'NaNaNaNa', 'HaKuNa']
symbols = ['Na','K','H']
for i in range(len(symbols)):
 for word in itertools.permutations(symbols,i+1):
  print( ''.join(word) )


def can_be_built(word):
  pos = 0
  ret = True
  while(pos < len(word)):
   #following loop checks if word starting form `pos`
   #can be prefixed by a symbol
   symbol_match = False
   for symbol in symbols:
    if word[pos:pos+len(symbol)] == symbol:
      symbol_match = True
      break
   if symbol_match == False:
     print('Word `{}` has no match for symbol from: {}'.format(word, word[pos:]))
     ret = False
     break
   #if it does move forward
   pos += len(symbol)

  return ret

for word in words:
   print("{} can be built? {}".format(word, can_be_built(word)))

它迭代地检查一个单词前缀是否为符号，然后向前移动直到单词的末尾被到达。

输出：

K can be built? True
NaH can be built? True
NaNaNaNa can be built? True
Word `HaKuNa` has no match for symbol from: aKuNa
HaKuNa can be built? False

它还不是完美的。

正确的方法

正如Makoto所说，前缀检查应该返回每个可能的匹配列表。算法应该将这些匹配项排入队列，并检查所有可能的路径。这有点像构建一个与单词匹配的前缀图。如果能构建整个单词，就成功了。

我认为修正我的第二个示例仍然相当容易，但是我没有时间编写实际的代码了。我认为这是一个很好的起点。

- luk32

请问您能详细说明一下您的解决方案吗？ - Ritesh

所以，您选择将周期表中的所有符号添加到字符串数组中。您的算法似乎非常特定于某种语言。 - Ritesh

我添加了第二个示例，以便蝙蝠侠可以重复说“NaNaNa”。这些示例是用Python编写的。 - luk32

我认为上面的代码有一定的意义。我会尝试它。谢谢！ - Ritesh

我已经编辑了代码并添加了注释以帮助识别前缀检查。但我认为最好重构它，而且你肯定需要让它捕获所有可能的匹配项，而不仅仅是当前的第一个。 - luk32

让你的测试100%正常工作的诀窍是检查前1或2个字符是否为有效的元素名称，并且余下的单词可以通过递归地从元素名称构建。这将是指数时间，但可以通过DP将其降至线性时间 - 请参见我的答案。 - j_random_hacker

0

[编辑：本帖子基本上只是对Niklas B.在其他帖子评论中提到的DP算法的全面解释。]

在线性时间内测试特定单词

在一个可以由化学元素名称组成的单词中，至少有以下一种情况为真：

最后一个字母是单个字母的化学元素名称，并且除了最后一个字母之外的前缀本身是可以由化学元素名称组成的单词。
最后两个字母是两个字母的化学元素名称，并且除了最后两个字母之外的前缀本身是可以由化学元素名称组成的单词。

这表明了一个很好的DP算法，对于给定长度为k的单词w，我们计算出所有1 <= i <= k的值，即w的长度-i前缀可以构建的最大字母数（或化学符号数；问题在于我们要最大化什么！）。让我们称之为f(i)，如果w的长度-i前缀根本不能从化学元素名称中构建，则将f(i) = -1。

让X = 1以最大化元素名称，或者X = 2以最大化字母计数。

DP的递归可以写成：

one(i) = 如果(w[i]是一个1个字母的元素名称){f(i-1)+1}否则{-1}
two(i) = 如果("w[i-1]w[i]"是一个2个字母的元素名称){f(i-2)+X}否则{-1}
f(i) = 如果i < 0，则为-1
f(0) = 0
f(i) = 如果i > 0，则为max(one(i), two(i))

那么f(k)就是我们想要知道的：可以从中形成的最大数量的(字母/元素)，如果不可能，则为-1。

max()表示如果只有一种处理前缀结尾的方法有效，那么将选择该方法(因为另一种方法的得分为-1，总是比较小)，如果两种方法都无效，我们将正确地得到f(i)=-1。

假设单个字符或字符对是否为有效化学元素名称的测试是常数时间(使用例如数组或哈希表查找)，我们可以计算给定单词是否可以表示为其长度成比例的化学元素名称序列的时间和空间。

考虑所有单词

如果我们要最大化字母数量，那么按照长度递减的顺序处理字典可能是最合理的，因为第一次遇到 f(k) 不等于 -1 的单词时，我们就知道它必须是最长的，可以停止处理。

这可以用于最大化元素名称计数。虽然我们不能立即停止，因为可能会有一个更短的单词在后面，但仍然可以从中获得一些有用的信息，特别是当我们发现一个新单词的元素计数比先前的最佳值更大时：我们可以使用此元素计数更新截止阈值，并在看到比此阈值更短的单词时停止，因为长度为 m 的单词永远无法从超过 m 个元素名称中形成。

还有一种不同的方法，可能会更快：通过首先按字母顺序对字典进行排序，我们可以避免在与前一个单词共享的前缀上重新计算 f(i)。例如，如果“carton”紧随“cart”之后出现在字典中，则我们只需要在“on”部分上计算 f(i)。

- j_random_hacker

-1

很抱歉，我对这些答案感到非常困惑。显然，最简单的方法是使用嵌套桶排序将字典按字母顺序排序，直到某个深度，比如8个字母，这样可以让你以顺序1检索以给定序列字母开头的单词，最多8个字母。

然后，像玩游戏树一样遍历周期表。在每一步中，您都会添加一个元素，然后向下检查列表，看是否有以该组合开头的单词。

这将相对较耗费内存，因为您可能需要至少6层桶（按前6个字母进行字母排序），但通常只有大约100万个单词。由于游戏树中几乎每个分支都会在四个字母后终止，因此您的DFS将非常快速地搜索整个游戏树。如果您可以形成字典中的每个单词，那么仍然必须存在与单词数量相同的分支数，实际上您只能获得字典中的一小部分单词，因此这种方法必须是有效的。

- phil_20686

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Makoto · Accepted Answer

我认为更好的方法是检查字典中的每个单词，看它是否可以由元素名称组成。检查元素的每个排列将更难编程且效率较低。

虽然我同意制作组合更容易，但是它们太多了，就像你说的，如果不给出限制，它们会趋近于无穷大。使用符号生成单词会稍微困难和棘手一些，但我认为这并不太难。

例如，当您获得一个单词时，您可以搜索元素，寻找可以构成您的单词的元素，然后使用该元素集尝试从头到尾填写字母。显然，对于长度不为2的元素和奇数长度的单词，这变得更加困难。

实际上，您可以使用一种图表。假设您有“硅”。您可以从字母“S”或“SI”开始，两者都在表格中。从那里选择“SI”，因为它更接近您的解决方案。如果“SI”不能导致您的解决方案，则必须回来查看“S”是否可行。

因此，它作为深度优先搜索的一种形式工作。