-1

Let's say I have the following two strings: "Hey there" and "there is a ball"

I want the output to be True, because the first one ends with "there" and the second one begins with "there".

Also, it would be helpful if I could know the length of the overlap.

jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
Javier Luna Molina
  • 62
  • 5

3 Answers3

3

This should work:

def endOverlap(a, b):
    for i in range(0, len(a)):
        if b.startswith(a[-i:]):
            return i
    return 0

a = "Hey there"
b = "there is a ball"
c = "here is a ball"
d = "not here is a ball"

print(a, b, endOverlap(a, b))
print(a, c, endOverlap(a, c))
print(a, d, endOverlap(a, d))

Edit: modified to return length of overlap and to be more efficient if only small parts of the string are expected to overlap. Then fixed a bug.

jojonas
  • 1,634
  • 14
  • 24
  • You could return the length of the overlap, rather than `True`/`False`, as an overlap of `0` (i.e. no overlap) would evaluate false-y in a boolean context. – jonrsharpe Sep 08 '15 at 13:14
  • OP specifically asked for boolean `True`, but of course you can modify it by returning `len(a)-i`. – jojonas Sep 08 '15 at 13:15
  • Indeed, that was based on *"Also, it would be helpful if I could know the length of the overlap."* – jonrsharpe Sep 08 '15 at 13:16
  • Yes, my mistake - `[-0:]` is actually the whole string, not `''`; I briefly thought it would *always* return `0`! – jonrsharpe Sep 08 '15 at 13:28
  • The `endOverlap` function will require exponential time because `b.startswith` requires runtime linear to the length of the given argument. Note how `b.startswith` is called repeatedly with every increasing string lengths; this is [Shlemiel's algorithm](http://en.wikichip.org/wiki/Schlemiel_the_Painter's_Algorithm). – Frerich Raabe Sep 08 '15 at 13:32
  • Yes, I suspect that there is a more efficient version, but I am not sure whether that would be overkill in OPs case. – jojonas Sep 08 '15 at 13:34
  • @jojonas The solution I propose uses less code and needs linear time. – Frerich Raabe Sep 08 '15 at 13:36
  • @FrerichRaabe You didn't propose a working solution. – jojonas Sep 08 '15 at 14:02
  • 1
    @jojonas Oops, indeed! I deleted my answer now, thanks for double-checking that! – Frerich Raabe Sep 09 '15 at 07:36
  • 1
    Now I actually wonder if there is a solution better than `O(n^2)` – jojonas Sep 09 '15 at 10:07
0
# do your str checks here...
if (str1.split()[-1] == str2.split()[0]):
taesu
  • 4,482
  • 4
  • 23
  • 41
  • This only works if the overlap is a whole word, which may not be the case – jonrsharpe Sep 08 '15 at 13:13
  • @jonrsharpe always appreciate your input, thanks. I notice it becomes much complicated when you consider character overlap – taesu Sep 08 '15 at 13:15
0

To know overlap of two strings use generator and endswith string method. The max value of this substring will be the max overlap:

>>> str1 = "Hey there"
>>> str2 = "there is a ball"
>>> overlap = max((str2[:x] for x in range(1,len(str2) + 1) if str1.endswith(str2[:x])),key = len)
>>> overlap
'there'

To return True use if statements or bool type:

>>> if overlap:
...     print True
... 
True
>>> bool(overlap)
True

To know the length just use len function:

>>> len(overlap)
5
Sdwdaw
  • 1,037
  • 7
  • 14
  • You should use `max((x for x in range....))`, this solution only works because `max(('foo', 'foob, 'foobar'))` is the longest word (they're compared alphabetically). – jojonas Sep 08 '15 at 13:50
  • `max` is used for repeating overlaps: `>>> str3 = '111'` `>>> str4 = '11111'` `>>> [str4[:x] for x in range(1,len(str4) + 1) if str3.endswith(str4[:x])]` `['1', '11', '111']` – Sdwdaw Sep 08 '15 at 13:55
  • Yes, and `max` will choose the alphabetically ordered last string. See (independent of your example) this example: `max(('aaaaaaa', 'b', 'c'))` will return `c` and *not* the longest string, which ould be `aaaaaaa`. – jojonas Sep 08 '15 at 13:58
  • 1
    Oops... Yes, max for strings returns alpha first meaning. Thanks, I should rewrite my solution. – Sdwdaw Sep 08 '15 at 14:01