剪枝相似字符串由长度

一个如何将消除可以通过相似性和长度包含从Python列表串的元素（如果字符串X在另一个发现，较长的字符串ÿ，X必须被移除）？剪枝相似字符串由长度

IN:  [('this is string that stays', 0), ('this is string', 1), ('string that stays', 2), ('i am safe', 3)] 
OUT: [('this is string that stays', 0), ('i am safe', 3)]

来源

2011-08-31 SomeOne

给出你的例子，''这是字符串''在** **中是**，这是一个字符串''。是因为第一个字符串中的每个单词出现在第二个字符串中？如果这不是拼写错误，请在**另一个字符串中指定一个字符串的含义是**。 –

更正了示例。 – SomeOne

好。你有什么想法吗？给我们一些讨论。 –

在这里你去：

l = [('this is string that stays', 0), ('this is string', 1), ('string that stays', 2), ('i am safe', 3)] 
survivors = set(s for s, _ in l) 
for s1, _ in l: 
if any(s1 != s2 and s1 in s2 for s2 in survivors): 
    survivors.discard(s1)

survivors是你想要的，但它不包含输入的元组号码 - 改变这应该是为读者:-P练习。

来源

2011-08-31 07:15:45

谢谢。我想我自己解决它：https://pzt.me/13gn – SomeOne

试试这个：

IN = [('this is string that stays', 0), ('this is string', 1), ('string that stays', 2), ('i am safe', 3)] 
OUT=[] 

def check_item(liste, item2check): 
    for item, _ in liste: 
     if item2check in item and len(item2check) < len(item): 
      return True 
    return False 

for item, rank in IN: 
    if not check_item(IN, item): 
     OUT.append((item, rank)) 

# or in a list-comprehension : 
OUT = [(item, rank) for item, rank in IN if not check_item(IN, item)] 
print OUT 

>>> [('this is string that stays', 0), ('i am safe', 3)]

来源

2011-08-31 07:20:05

，如果你不介意的顺序（N * N）

>>> s=[('this is string that stays', 0), ('this is string', 1), ('string that stays', 2), ('i am safe', 3)] 
>>> s=[i[0] for i in s] 
>>> result=[s[i] for i in range(len(s)) if not any(s[i] in s[j] for j in range(i)+range(i+1,len(s)-i))] 
>>> result 
['this is string that stays', 'i am safe']

如果你关心效率，我建议你每个字符串分割成的序列字（或甚至字符）并且制作树数据结构，例如trie（http://community.topcoder.com/tc?module=Static &d1 = tutorials &d2 = usingTries），其允许在每个子序列上快速查找

来源

2011-08-31 07:22:40

所有其他答案都提供了很好的解决方案。我只想补充您尝试记：

for i in range(0, len(d)): 
    for j in range(1, len(d)): 
    if d[j][0] in d[i][0] and len(d[i][0]) > len(d[j][0]): 
     del d[j]

失败与列表索引超出范围，因为遍历目录，而你删除。这里有一种方法可以防止这个问题：

d = [('this is string that stays', 0), ('this is string', 1), ('string that stays', 2), ('i am safe', 3)] 

to_be_removed = list() 
for i in range(0, len(d)): 
    for j in range(0, len(d)): 
    if i != j and d[j][0] in d[i][0] and len(d[i][0]) > len(d[j][0]): 
     to_be_removed.append(j) 
for m, n in enumerate(to_be_removed): 
    del d[n - m] 

print d

来源

2011-08-31 07:36:11 MarcoS

剪枝相似字符串由长度

回答

相关问题