给定一个字符串列表，判断一个字符串是否是另一个字符串的前缀

Question

我想写一个Python函数来检查一个字符串是否是另一个字符串的前缀字符串;不是另一个的任意子字符串;必须是前缀。如果是，则返回True。例如，

list = ['abc', 'abcd', 'xyx', 'mno']

返回True，因为'abc'是'abcd'的前缀。

list = ['abc', 'xyzabc', 'mno']

返回False

我尝试了startwith()和列表理解，但它没有完全工作。感谢您的帮助和指点。

Answer 1

让我们首先对字符串的给定lst w.r.t长度进行排序，因为已知的事实是子字符串的长度总是小于或等于原始字符串，所以在排序之后，我们在列表的开头有长度较小的字符串，然后我们在排序后的列表中迭代，比较当前元素与它旁边的所有元素。这个小小的优化将降低问题的复杂性，因为现在我们不必将每个元素与其他元素进行比较。

lst1 = ['abc', 'abcd', 'xyx', 'mno']
lst2 = ['abc', 'xyzabc', 'mno']
lst3 = ["abc", "abc"]
def check_list(lst):
    lst = list(set(lst))    #if you want to avoid redundant strings.
    lst.sort(key = lambda x:len(x))
    n = len(lst)
    for i in xrange(n):
        for j in xrange(i+1, n):
            if lst[j].startswith(lst[i]):
                return True
    return False
print check_list(lst1)
print check_list(lst2)
print check_list(lst3)
>>> True
>>> False
>>> False #incase you use lst = list(set(lst))

Answer 2

使用itertools

import itertools
list1 = ["abc", "xyz", "abc123"]
products = itertools.product(list1, list1)
is_substringy = any(x.startswith(y) for x, y in products if x != y)

这不是很优化，但取决于你要处理的数据量，代码是相当优雅的(和短);在您的用例中，这可能胜过速度。

这里假设列表中没有纯重复(但在您的示例中没有)。

Answer 3

import itertools
mlist = ['abc', 'abcd', 'xyx', 'mno']
#combination of list elements, 2-by-2. without repetition  
In [638]: for i,j in itertools.combinations(mlist,2):
    print (i,j)
   .....:     
('abc', 'abcd')
('abc', 'xyx')
('abc', 'mno')
('abcd', 'xyx')
('abcd', 'mno')
('xyx', 'mno')
#r holds the final result. if there is any pair where one is a prefixed of another 
r=False
In [639]: for i,j in itertools.combinations(mlist,2):  
    r = r or i.startswith(j) # if i is the prefix of j. logical or
    r = r or j.startswith(i) # if j is the prefix of i
   .....:     
In [640]: r
Out[640]: True