将列表与长文本的精确匹配或打乱匹配进行比较

Question

我有以下列表，我想迭代它，并查找是否有与长字符串aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt的争夺匹配，并返回匹配的数量。下面的例子应该返回4

混乱字符串基本上以相同的字母开始和结束，其余字母重新排列。

long_string = 'aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt'
my_list = [
'axpaj', # this is scrambled version of aapxj
'apxaj', # this is scrambled version of aapxj
'dnrbt', # this is exact match of dnrbt
'pjxdn', # this is scrambled version of pxjdn
'abd',
]
matches = 0
for l in my_list:
# check for exact match
if l in long_string:
matches += 1
# check for a scramble match
# ...
# matches = 1. Wrong should be 4.

def is_anagram(str1, str2):
str1_list = list(str1)
str1_list.sort()
str2_list = list(str2)
str2_list.sort()
return (str1_list == str2_list)

is_anagram('axpaj' , 'aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt')
['a', 'a', 'j', 'p', 'x']
['a', 'a', 'b', 'b', 'b', 'b', 'b', 'b', 'b', 'd', 'd', 'd', 'd', 'd', ...]

Answer 1

这将为所需的每个不同单词长度创建排序匹配字符串。它在运行中构建它们以避免过多的处理。(编辑:哎呀，以前的版本假设一个长字符串在做缓存。谢谢你，@BeRT2me!)

long_string = 'aapxjdnrbtvldptfzbbdbbzxtndrvjblnzjfpvhdhhpxjdnrbt'
my_list = [
'axpaj', # this is scrambled version of aapxj
'apxaj', # this is scrambled version of aapxj
'dnrbt', # this is exact match of dnrbt
'pjxdn', # this is scrambled version of pxjdn
'abd',
]
anagrams = {}  # anagrams contains sorted slices for each word length
def is_anagram(str1,str2):
lettercount = len(str1)
cachekey = (str2,lettercount)
if cachekey not in anagrams:
# build the list for that letter length
anagrams[cachekey] = [sorted(str2[x:x+lettercount]) for x in range(len(str2)-lettercount+1)]
return (sorted(str1) in anagrams[cachekey])

matches = 0
for l in my_list:
if is_anagram(l,long_string):
matches += 1
print (f"There are {matches} in my list.")

Answer 2

我认为找到解决方案的第一步是编写代码，切断字符串的第一个和最后一个字母。

someFunction("abcde") should return "bcd"

接下来，您需要某种方法来检查字符串中的字母是否都相同。我将通过按字母顺序排列并比较相应的元素来实现这一点。

alphabetize("khfj") gives "fhjk"
isSame("abc","abc") gives True

那么你需要一种方法将字符串切割成指定长度的每个子字符串，例如:

thisFunction("abcdef", 2) gives ["ab", "bc", "cd", "de", "ef"]

一旦你有了所有可能的长度子字符串，你可以通过检查列表中的每个项目与long_string中具有相同长度的每个子字符串来检查混乱匹配

Answer 3

这是一个基本的方法-迭代long_string的所有子字符串与匹配的长度，并检查它们在排序后是否等于搜索项。

matches = 0
for x in my_list:

# simple case 1: exact match
if x in long_string:
matches += 1
continue

# sort the string - returns a list
x = sorted(x)

# simple case 2: exact match after sorting
if ''.join(x) in long_string:
matches += 1
continue

window_size = len(x)

for i in range(len(long_string)-window_size):

# sort the substring
y = sorted(long_string[i:i+window_size])
# compare - note that both x and y are lists, 
# but it doesn't make any difference for this purpose
if x == y:
matches += 1
break

注意，这不是很有效，因为子字符串在每个循环中都要重新排序。一种简单的优化方法是将排序后的子字符串存储在字典中，该字典将子字符串长度映射到排序后的子字符串集合({4: {'aapx', 'ajpx', 'djpx', ...}})。

Answer 4

使用一点正则表达式，可以得到一个有趣的解决方案:

• 查找匹配的字符串:
  • 开始和结束相同。
  • 长度相同
  • 只包含与子列表相同的内部字母。
• 检查排序项是否与排序子字符串匹配。并且它们不匹配未排序的。

import re
def is_anagram(str1, str2):
return sorted(str1) == sorted(str2) and str1 != str2
def get_matches(str1, str2):
start, middle, end = str1[0], str1[1:-1], str1[-1]
pattern = fr'{start}[{middle}]{{{len(middle)}}}{end}'
return re.findall(pattern, str2)
matches = 0
for l in my_list:
for item in get_matches(l, long_string):
if is_anagram(item, l):
matches += 1
print(matches)
# Output:
4