Python - 列表上的简单算法任务(求职面试的标准问题)

Question

有2个输入列表L和M,例如:

L =  ['a',     'ab',  'bba']
M = ['baa', 'aa',  'bb']

如何获得2个非空输出列表U和V,使得: ''.join(U) == ''.join(V)) is True和U的每个元素都在L中,并且V的每个元素都在M中？

例如,上面两个输入列表的一种可能解决方案是:

U=['bba', 'ab', 'bba', 'a']
V=['bb', 'aa', 'bb', 'baa']

因为

 'bbaabbbaa' == 'bbaabbbaa' is True

和 every element of ['bba', 'ab', 'bba', 'a'] is in ['a', 'ab', 'bba']

和 every element of ['bb', 'aa', 'bb', 'baa'] is in ['baa', 'aa', 'bb']

1)创建一个算法,找到至少一个解(U和V).

2)它可以在O(n)中求解,其中n = len(L + M)？

:WQ

Answer 1

你在寻找什么 - 所有(可数无数)可能的解决方案？"最短"(通过某种程度)非空解决方案,或一组等于最短的解决方案,或......？

因为,如果有任何解决方案,将U和V都设置为[]符合所有规定的条件,并且是O(1)启动;-).

编辑:好的,所以,开玩笑,这是一个很好的对称解决方案,打印前十个可数无限的非空解决方案:

import itertools as it
import collections

L = ['a', 'ab', 'bba']
M = ['baa', 'aa', 'bb']

def cmbs(L=L, M=M):
  Ucans = collections.defaultdict(list)
  Vcans = collections.defaultdict(list)
  sides = (L, Vcans, Ucans), (M, Ucans, Vcans)
  for i in it.count(1):
    for k, (G, Ocans, Tcans) in enumerate(sides):
      for u in it.product(G, repeat=i):
        j = ''.join(u)
        if j in Ocans:
          for samp in Ocans[j]:
            result = samp, u
            yield result[1-k], result[k]
        Tcans[j].append(u)

if __name__ == '__main__':
  for x, y in it.islice(cmbs(), 10):
    print x, y, ''.join(x), ''.join(y)

发出的

('a', 'a') ('aa',) aa aa
('bba', 'a') ('bb', 'aa') bbaa bbaa
('a', 'a', 'a', 'a') ('aa', 'aa') aaaa aaaa
('a', 'a', 'bba', 'a') ('aa', 'bb', 'aa') aabbaa aabbaa
('a', 'ab', 'a', 'a') ('aa', 'baa') aabaa aabaa
('a', 'ab', 'bba', 'a') ('aa', 'bb', 'baa') aabbbaa aabbbaa
('bba', 'a', 'a', 'a') ('bb', 'aa', 'aa') bbaaaa bbaaaa
('bba', 'ab', 'a', 'a') ('bb', 'aa', 'baa') bbaabaa bbaabaa
('bba', 'ab', 'bba', 'a') ('bb', 'aa', 'bb', 'baa') bbaabbbaa bbaabbbaa
('bba', 'a', 'bba', 'a') ('bb', 'aa', 'bb', 'aa') bbaabbaa bbaabbaa

我不确定O(N)在可数无限解决问题的背景下是什么意思 - N应该在这里是什么？! - )

编辑2:更改为使用(默认)列表的序列,以确保它找到所有解决方案,即使可以从输入集合之一以> 1方式创建相同的连接字符串(样本输入中未发生的条件,所以样本输出不受影响); 例如,如果L ['a', 'aa']显然是任何连接的字符串> 1 a可以以多种方式制作 - 当这样的连接字符串匹配为M制作的字符串时,当前解决方案将发出所有这些多种方式,而前一个字符串只发出一个他们.