Menu
I'd like to compare 2 strings and keep the matched, splitting off where the comparison fails.
So if I have 2 strings -
string1 = apples string2 = appleses answer = apples Another example, as the string could have more than one word.
string1 = apple pie available string2 = apple pies answer = apple pie I'm sure there is a simple Python way of doing this but I can't work it out, any help and explanation appreciated.
864
To find common substrings between two strings with Python, we can use the difflib module. We have 2 strings string1 and string2 that we want to find the common substring that's in both strings. To do that, we use the SequenceMatcher class with string1 and string2 .
Naive Approach: Let strings X and Y be the lengths m and n respectively. Generate all possible substrings of X which requires a time complexity of O(m2) and search each substring in the string Y which can be achieved in O(n) time complexity using the KMP algorithm. Overall time complexity will be O(n * m2).
Approach: Count the frequencies of all the characters from both strings. Now, for every character if the frequency of this character in string s1 is freq1 and in string s2 is freq2 then total valid pairs with this character will be min(freq1, freq2). The sum of this value for all the characters is the required answer.
For completeness, difflib in the standard-library provides loads of sequence-comparison utilities. For instance find_longest_match which finds the longest common substring when used on strings. Example use:
from difflib import SequenceMatcher string1 = "apple pie available" string2 = "come have some apple pies" match = SequenceMatcher(None, string1, string2).find_longest_match(0, len(string1), 0, len(string2)) print(match) # -> Match(a=0, b=15, size=9) print(string1[match.a: match.a + match.size]) # -> apple pie print(string2[match.b: match.b + match.size]) # -> apple pie If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
