擅长:python、mysql、java
<p>问题是:检查列表中的所有单词是否显示为另一个列表中的单词中至少一个单词的开头。你知道吗</p>
<p>假设op希望S1中的所有单词至少作为S2中单词的开头出现一次。你知道吗</p>
<p>您可以对两个输入进行排序</p>
<pre><code>def contain(s1, s2):
count = 0
for i in s1:
while ( count < len(s2) and s2[count].startswith(i) == False ):
count += 1
if (count >= len(s2)): return False
return True
s1 = sorted(set(['red', 'gold', 'black', 'gold', 'red', 're']))
s2 = sorted(['golden', 'blackstone', 'golden', 'goldlike', 'blackstone', 'golden', 'redline', 'red'])
print( contain(s1, s2) )
</code></pre>
<p>输出:</p>
<p><code>True</code></p>
<p><strong><em>编辑以包含复杂性:</em></strong></p>
<p>假设S1有<code>n</code>个元素,S2有<code>m</code>个元素。你知道吗</p>
<p>如果一个简单的解决方案有嵌套的循环来遍历这两个列表,那么它的复杂性将是<code>O(n*m)</code>。你知道吗</p>
<p>通过对S1和S2进行排序,我们可以降低求解的复杂性。你知道吗</p>
<p>排序S1:<code>O(n*log n)</code>,排序S2:<code>O(m*log m)</code>,包含:<code>O(m)</code>(<code>m if m > n else n</code>)</p>
<p>正如Stefan在评论中指出的,通过排序,它将比单纯的方法具有更好的复杂性。你知道吗</p>