从perodic表元素形成算法最大的字

问题描述

我想要写一个算法以下问题方案

I want to write an algorithm for the following problem scenario

以元素周期表的名称，发现可以形成最大的字？如娜，氖等符号应当被视为单独的元素。

Taking periodic table elements' names, find largest word that can be formed?The symbols such as Na , Ne etc should be regarded as single elements.

这是在问一个知名公司的面试。任何人都可以请帮我解决这个问题。

This was asked in a reputed company's job interview.Can anybody please help me out solve this.

推荐答案

：

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

您可以生成各种可能的组合，并核对字典如果一个acutal字。但是，如果你允许没有重复的符号是效率低下，只为。

You can generate every possible combination, and check against a dictionary if its an acutal word. But it is inefficient and only for if you allow no repetitions of symbols.

如果你让你需要检查一个字对符号列表重复。我提出以下建议：

If you allow repetitions you need to check a word against the list of symbols. I propose the following:

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)))

据重复检查，如果一个字preFIX是一个符号，然后向前移动，直到字的末尾。

It iteratively check if a word prefix is a symbol, then moves forward until the end of word is reached.

输出：

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

它仍然是不完美的。

It still is not perfect.

由于诚说，在preFIX检查应返回的每一个可能的比赛名单。该算法应该做一个队列掉那些比赛，并检查所有可能的路径。这将是一种像建筑相匹配，这个词prefixes图。如果一个人建立整个单词你回家。

As Makoto says, the prefix-check should return a list of every possible match. The algorithm should make a queue out of those matches, and check all possible paths. It would be kind of like building a graph of prefixes that match the word. And if one builds whole word you are home.

我觉得还是比较容易纠正我的第二个例子，但我出来的时候实际code。我认为这是开始的好地方。

I think it is still fairly easy to correct my 2nd example, but I am out of time for the actual code. I think it's a good place for start.

这篇关于从perodic表元素形成算法最大的字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！