根據元素子串減少列表

我正在尋找最有效的方法來根據列表中已有的子字符串來減少給定列表。因爲兩個 'ABCD' 和 'QRS' 是在該列表中的其他元素的最小的子串根據元素子串減少列表

mylist = ['abcd','qrs']

：

例如

mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu']

將減少到。我能夠用大約30行代碼做到這一點，但我懷疑有一個狡猾的單行程在那裏..

來源

2017-06-13 Chris Hall

在高層次上，很簡單：建立一個[基數樹]（https://en.wikipedia.org/wiki/Radix_tree），然後把根的直接子代（代表實際元素;一個節點只是其desendents的最大公共前綴）。在實踐中，你需要追蹤基數樹的體面實現。 [這個問題]（https://stackoverflow.com/questions/4707296/are-there-any-radix-patricia-critbit-trees-for-python）可能會幫助你開始。 – chepner

你能提供更復雜的測試例子嗎？ –

子串是否應該是前綴？ – DyZ

這似乎是工作（但並非如此高效我想）

def reduce_prefixes(strings): 
    sorted_strings = sorted(strings) 
    return [element 
      for index, element in enumerate(sorted_strings) 
      if all(not previous.startswith(element) and 
        not element.startswith(previous) 
        for previous in sorted_strings[:index])]

測試：

>>>reduce_prefixes(['abcd', 'abcde', 'abcdef', 
        'qrs', 'qrst', 'qrstu']) 
['abcd', 'qrs'] 
>>>reduce_prefixes(['abcd', 'abcde', 'abcdef', 
        'qrs', 'qrst', 'qrstu', 
        'gabcd', 'gab', 'ab']) 
['ab', 'gab', 'qrs']

來源

2017-06-13 17:22:36

對字符串進行預先排序是一個聰明的技巧，與我的天真解決方案相比，這可能會大大加快它的速度。 –

一個解決方案是遍歷所有的字符串，並根據它們是否有不同的字符並遞歸地應用該函數。

def reduce_substrings(strings): 
    return list(_reduce_substrings(map(iter, strings))) 

def _reduce_substrings(strings): 
    # A dictionary of characters to a list of strings that begin with that character 
    nexts = {} 
    for string in strings: 
     try: 
      nexts.setdefault(next(string), []).append(string) 
     except StopIteration: 
      # Reached the end of this string. It is the only shortest substring. 
      yield '' 
      return 
    for next_char, next_strings in nexts.items(): 
     for next_substrings in _reduce_substrings(next_strings): 
      yield next_char + next_substrings

此將其分解成基於字符的字典，並試圖找到最短的子串出來的，它在字典中分裂成不同的列表。

當然，由於這個函數的遞歸性質，單線程將不可能有效。

來源

2017-06-13 16:54:31 Artyer

-1

試試這個：

import re 
mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu'] 
new_list=[] 
for i in mylist: 
    if re.match("^abcd$",i): 
     new_list.append(i) 
    elif re.match("^qrs$",i): 
     new_list.append(i) 
print(new_list) 
#['abcd', 'qrs']

來源

2017-06-13 17:12:43

這裏假定列表的值是已知的。值將是未知的，值不能在列表中的其他項目是該項目的子字符串 –

我明白了。謝謝。 –

也許不是最有效的，但至少短：

mylist = ['abcd','abcde','abcdef','qrs','qrst','qrstu'] 

outlist = [] 
for l in mylist: 
    if any(o.startswith(l) for o in outlist): 
     # l is a prefix of some elements in outlist, so it replaces them 
     outlist = [ o for o in outlist if not o.startswith(l) ] + [ l ] 
    if not any(l.startswith(o) for o in outlist): 
     # l has no prefix in outlist yet, so it becomes a prefix candidate 
     outlist.append(l) 

print(outlist)

來源

2017-06-13 17:26:52

根據元素子串減少列表

回答

相關問題