Comment trouver toutes les intersections (également appelées les sous-chaînes communes les plus longues) de deux chaînes et leurs positions dans les deux chaînes?
Par exemple, si S1="never"
et S2="forever"
, l'intersection résultante doit être ["ever"]
et ses positions sont [(1,3)]
. Si S1="address"
et S2="oddness"
, les intersections résultantes sont ["dd","ess"]
et leurs positions sont [(1,1),(4,4)]
.
La solution la plus courte sans inclure de bibliothèque est préférable. Mais toute solution correcte est également la bienvenue.
6 réponses
Eh bien, vous dites que vous ne pouvez inclure aucune bibliothèque. Cependant, le difflib standard de Python contient une fonction qui fait exactement ce que vous attendez. Étant donné qu'il s'agit d'une question d'entrevue Python, la familiarité avec difflib pourrait être ce à quoi l'intervieweur s'attendait.
In [31]: import difflib
In [32]: difflib.SequenceMatcher(None, "never", "forever").get_matching_blocks()
Out[32]: [Match(a=1, b=3, size=4), Match(a=5, b=7, size=0)]
In [33]: difflib.SequenceMatcher(None, "address", "oddness").get_matching_blocks()
Out[33]: [Match(a=1, b=1, size=2), Match(a=4, b=4, size=3), Match(a=7, b=7, size=0)]
Vous pouvez toujours ignorer le dernier tuple Match, car il est factice (selon la documentation).
Je suppose que vous ne voulez que les sous-chaînes correspondent si elles ont la même position absolue dans leurs chaînes respectives. Par exemple, "abcd" et "bcde" n'auront aucune correspondance, même si les deux contiennent "bcd".
a = "address"
b = "oddness"
#matches[x] is True if a[x] == b[x]
matches = map(lambda x: x[0] == x[1], zip(list(a), list(b)))
positions = filter(lambda x: matches[x], range(len(a)))
substrings = filter(lambda x: x.find("_") == -1 and x != "","".join(map(lambda x: ["_", a[x]][matches[x]], range(len(a)))).split("_"))
Positions = [1, 2, 4, 5, 6]
Substrings = ['dd', 'ess']
Si vous ne voulez que des sous-chaînes, vous pouvez les écraser sur une seule ligne:
filter(lambda x: x.find("_") == -1 and x != "","".join(map(lambda x: ["_", a[x]][map(lambda x: x[0] == x[1], zip(list(a), list(b)))[x]], range(len(a)))).split("_"))
Batteries incluses!
Le module difflib pourrait vous aider - voici un diff côte à côte rapide et sale:
>>> import difflib
>>> list(difflib.ndiff("never","forever"))
['- n', '+ f', '+ o', '+ r', ' e', ' v', ' e', ' r']
>>> diffs = list(difflib.ndiff("never","forever"))
>>> for d in diffs:
... print {' ': ' ', '-':'', '+':' '}[d[0]]+d[1:]
...
n
f
o
r
e
v
e
r
Cela peut être fait dans O (n + m) où n
et m
sont des longueurs de chaînes d'entrée.
Le pseudocode est:
function LCSubstr(S[1..m], T[1..n])
L := array(1..m, 1..n)
z := 0
ret := {}
for i := 1..m
for j := 1..n
if S[i] = T[j]
if i = 1 or j = 1
L[i,j] := 1
else
L[i,j] := L[i-1,j-1] + 1
if L[i,j] > z
z := L[i,j]
ret := {}
if L[i,j] = z
ret := ret ∪ {S[i-z+1..z]}
return ret
Consultez l'article Longest_common_substring_problem wikipedia pour plus de détails.
def IntersectStrings( first, second):
x = list(first)
#print x
y = list(second)
lst1= []
lst2= []
for i in x:
if i in y:
lst1.append(i)
lst2 = sorted(lst1) + []
# This above step is an optional if it is required to be sorted alphabetically use this or else remove it
return ''.join(lst2)
print IntersectStrings('hello','mello' )
Voici ce que je pourrais trouver:
import itertools
def longest_common_substring(s1, s2):
set1 = set(s1[begin:end] for (begin, end) in
itertools.combinations(range(len(s1)+1), 2))
set2 = set(s2[begin:end] for (begin, end) in
itertools.combinations(range(len(s2)+1), 2))
common = set1.intersection(set2)
maximal = [com for com in common
if sum((s.find(com) for s in common)) == -1 * (len(common)-1)]
return [(s, s1.index(s), s2.index(s)) for s in maximal]
Vérification de certaines valeurs:
>>> longest_common_substring('address', 'oddness')
[('dd', 1, 1), ('ess', 4, 4)]
>>> longest_common_substring('never', 'forever')
[('ever', 1, 3)]
>>> longest_common_substring('call', 'wall')
[('all', 1, 1)]
>>> longest_common_substring('abcd1234', '1234abcd')
[('abcd', 0, 4), ('1234', 4, 0)]
Questions connexes
De nouvelles questions
python
Python est un langage de programmation multi-paradigme, typé dynamiquement et polyvalent. Il est conçu pour être rapide à apprendre, comprendre, utiliser et appliquer une syntaxe propre et uniforme. Veuillez noter que Python 2 est officiellement hors support à partir du 01-01-2020. Néanmoins, pour les questions Python spécifiques à la version, ajoutez la balise [python-2.7] ou [python-3.x]. Lorsque vous utilisez une variante Python (par exemple, Jython, PyPy) ou une bibliothèque (par exemple, Pandas et NumPy), veuillez l'inclure dans les balises.