在Python中，如何检查字符串以查看是否有其他字符串的任何组合？

我有一个170 000单词列表，我正在写一个算法，使用每个单词的图形来查看最长的单词链可能;在Python中，如何检查字符串以查看是否有其他字符串的任何组合？

字链是词的列表，其中第i个字是第（i - 1）个字与一个额外的字符和其它字符被以任意方式布置

A - > AN - > CAN - >甘蔗

现在我有按字母顺序排列像CAT的所有单词= ACT

，我说加一个边缘时，字符串2包含字符串1，加一个其它字符

然而，在的情况下，

A-> AT - > ACT

AT和ACT之间的边缘，而不是绘制因为C分裂在A和T我如果要是“AT”发现语句只。

如何告诉python搜索一个字符串，以便字符顺序无关紧要？

来源

2015-10-14 Dan Nguyen

你关心字符串中的重复字符吗？比较caat和act时的例子。 –

您可以尝试按字母顺序排序字母。 – reticentroot

如果订单无关紧要，请使用[Counter]（https：//docs.python。org/3/library/collections.html＃collections.Counter）而不是字符串。然后你可以采用multiset交叉。 – Kevin

str1 = 'A' 
str2 = 'T' 
searchstring = 'ACT' 

if str1 in searchstring and str2 in searchstring: 
    print('it matched') 


# bigger example 

str1 = 'AT' 
searchstring = 'ACT' 
matches = [a for a in str1 if a in searchstring] 
if len(matches) == len(searchstring): 
    print('it matched')

来源

2015-10-14 02:05:32 tlastowka

假设两个字符串具有相似的长度，构造'matches'是字符串长度的二次方。其他答案更具性能。 – Kevin

不会从我这里得到任何争论。 – tlastowka

您可以创建一组两个字符串：

set1 = set(string1) 
set2 = set(string2)

，然后看看string1包含一切的在string2

set1.issubset(set2) # => returns True if set2 contains everything from set1

来源

2015-10-14 02:06:25 javanut13

我喜欢我在python中整天使用set，从来没有想过要设置一个字符串。不错。 – tlastowka

请注意这会匹配'CAAT'到'ACT'，不确定它们是否匹配。 –

我在OP的上一个重复问题中提出了这个确切的方法，并且被正确地告知它不起作用。 – TigerhawkT3

您可以使用collections.Counter和两个字符串转换成它（它会计算字符串中的字母），然后你可以比较它是否相等。示例 -

s1 = 'ACT' 
s2 = 'CAT' 
from collections import Counter 
if Counter(s1) == Counter(s2): 
    #Do stuff

演示 -

>>> s1 = 'ACT' 
>>> s2 = 'CAT' 
>>> from collections import Counter 
>>> Counter(s1) == Counter(s2) 
True

如果你想检查是否一个字符串包含在另一个，而无需关心顺序，可以如下使用any()内置功能 -

s1 = 'AXCT' 
s2 = 'CAT' 
A = Counter(s1) 
B = Counter(s2) 
if not any(count > A.get(b, 0) for b,count in B): 
    #Do stuff.

或者您还可以执行以下操作（如@Kevin in the comments所示） -

s1 = 'AXCT' 
s2 = 'CAT' 
A = Counter(s1) 
B = Counter(s2) 
if (B & A) == B: 
    #Do stuff

来源

2015-10-14 02:07:39

也可能想演示如何使用'＆'（例如'A＆B == A'）来检查子集。 – Kevin

有趣，它适合我。尝试'计数器（'ACT'）＆计数器（'ACTE'）==计数器（'ACT'）';我在3.4.3中得到了True。 – Kevin

@凯文哦，是的，'A'是子集。 –

您可以将较长的字符串转换为正则表达式，然后将其匹配。一个简单的方法是让所有的角色可选，其首先检查目标串是一个字符长：

def can_reach(frm, to): 
    if len(to) != len(frm) + 1: return False 
    if not re.fullmatch(re.sub(r'(.)', r'\1?', to), frm): return False 
    return True

如果你没有的Python 3.4，然后使用一个明确的$锚：

def can_reach(frm, to): 
    if len(to) != len(frm) + 1: return False 
    if not re.match(re.sub(r'(.)', r'\1?', to) + '$', frm): return False 
    return True

来源

2015-10-14 03:51:30 rici

在Python中，如何检查字符串以查看是否有其他字符串的任何组合？

回答

相关问题