我想要写一个算法以下问题方案
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.