有效检查一个字符串是否包含另一个字符串

Question

我有两个字符串：一个字和一个字母串。我想看看这些乱七八糟的信件是否有足够的字母来拼出单词。我想出了一个算法来做到这一点，但效率不够高，我希望能够得到一些帮助，使其更快。

这是我到目前为止有：

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 

temp = list(s1) 
for X in s2: 
    for Y in temp: 
     if X == Y: 
      temp.remove(X) 
      X = '@' 
if temp == []: 
    print('Found ', s1) 

我这里曾经X匹配我需要增加X，但我不知道如何，所以我只是把它的方程通过成为一个问题在符号。我尝试过使用break，但是达不到足以打破s2循环。无论哪种方式，我敢肯定，这个双重循环的想法是相比有经验的人会使用超级慢。有任何想法吗？

Answer 1

您的代码效率不高，不，因为您在双循环中迭代。对于s1中的每个字母，在最坏的情况下（无匹配），您将遍历所有的s2。

改为使用Counter object;这些充当多套，在那里你既可以测试，如果一个角色出现在O（1）时间和管理剩余计数：

from collections import Counter 

def contains(s1, s2): 
    s2set = Counter(s2) 
    for c in s1: 
     count = s2set[c] 
     if not c: 
      return False 
     if count == 1: 
      del s2set[c] 
     else: 
      s2set[c] = count - 1 
    return True 

你也可以把s1成多套，并检查如果为s2多组包含为每个条目足够的字母：

def contains(s1, s2): 
    s1set = Counter(s1) 
    s2set = Counter(s2) 
    for c, count in s1set.items(): 
     if count > s2set[c]: 
      return False 
    return True 

后者可进一步与all() function降低，这早返回False如果任何它被传递的结果是False，True otherw ISE：

def contains(s1, s2): 
    s2set = Counter(s2) 
    return all(count <= s2set[c] for c, count in Counter(s1).items()) 

在所有这些，你只需要遍历两s1和s2一次（直接或产生多组）。

后者的演示：

>>> from collections import Counter 
>>> def contains(s1, s2): 
...  s2set = Counter(s2) 
...  return all(count <= s2set[c] for c, count in Counter(s1).items()) 
... 
>>> s1 = 'hypochondriac' 
>>> s2 = 'yqhpwoewnqlchpijcdrxpoa' 
>>> contains(s1, s2) 
True 
>>> contains(s1 + 'b', s2) 
False 

Answer 2

做它的其他方式轮。从s2删除字符：

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 

temp = list(s2) 
try: 
    for ch in s1: 
     temp.remove(ch) 
except ValueError: 
    print("not found") 
else: 
    print("found", s1) 

Answer 3

扩展@Martijn_Pieters解决方案，您可以以这种方式使用Counter：

from collection import Counter 
def contains(s1, s2): 
    c1, c2 = Counter(s1), Counter(s2) 
    return all(c1[c] <= c2[c] for c in s1) 

你可以依靠的事实Counter[key]将默认为返回0，如果key不存在。

Answer 4

或从其他途径

s1 = 'hypochondriac' 
s2 = 'yqhpwoewnqlchpijcdrxpoa' 


for i in s1: 
    if not i in s2: 
     print 'not found' 

Answer 5

这里解决这个问题是使用NumPy一个量化的方法 -

import numpy as np 

def in_string(s1,s2): 
    arr1 = np.fromstring(s1, dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    return np.in1d(arr1,arr2).all() 

采样运行 -

In [50]: in_string('hypochondriac','yqhpwoewnqlchpijcdrxpoa') 
Out[50]: True 

# Let's add in a `z` at the end of first word which isn't in the scramble 
In [51]: in_string('hypochondriacz','yqhpwoewnqlchpijcdrxpoa') 
Out[51]: False 

---

这里的另一个NUMP基于Y的一个使用np.searchsorted -

def in_string_v2(s1,s2): 
    arr1 = np.fromstring(s1, dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    u1 = np.unique(arr1) 
    u2 = np.unique(arr2) 
    return ~(np.searchsorted(u2,u1) == np.searchsorted(u2,u1,'right')).any() 

---

这里是另外一个，一次处理一个单词列表中一个违背一个争夺 -

def in_string_v3(list_s1,s2): 
    l_arr1 = np.fromstring("".join(list_s1), dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    lens = np.array(map(len,list_s1)) 
    comp_lens = np.in1d(l_arr1,arr2).cumsum()[lens.cumsum()-1] 
    calc_lens = np.append(comp_lens[0],comp_lens[1:]-comp_lens[:-1]) 
    return lens == calc_lens 

采样运行 -

In [185]: ls1 = ['hypochondriac','hypochondriachsdhsahdsadhsa','hihfheifheozz'] 

In [186]: s2 = 'yqhpwoewnqlchpijcdrxpoadjksdgdkjsfkbdsfbdsdsaduiawyei' 

In [187]: in_string_v3(ls1,s2) 
Out[187]: array([ True, True, False], dtype=bool) 

还有一个以不同的方式处理单词列表 -

def in_string_v4(list_s1,s2): 
    l_arr1 = np.fromstring("".join(list_s1), dtype=np.uint8) 
    arr2 = np.fromstring(s2, dtype=np.uint8) 
    lens = np.array(map(len,list_s1)) 
    clens = lens.cumsum() 
    non_matching_idx = np.nonzero(~np.in1d(l_arr1,arr2))[0] 
    non_matching_grp = np.unique(clens.searchsorted(non_matching_idx)) 
    return ~np.in1d(np.arange(len(list_s1)),non_matching_grp)