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

Question

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

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

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

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

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

因为

 'bbaabbbaa' == 'bbaabbbaa' is True

and ['bba', 'ab', 'bba', 'a'] 的每个元素都在 ['a', 'ab', 'bba'] 中

并且['bb', 'aa', 'bb', 'baa']的每个元素都在['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 制作的字符串匹配时，所有这些多种方式，而前一个只发出其中之一。