在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中，如何檢查字符串以查看是否有其他字符串的任何組合？

回答

相關問題