Home > database >  The longest prefix that is also suffix of two lists
The longest prefix that is also suffix of two lists

Time:06-20

So I have two lists: def function(w,w2): => this is how I want to define my function (no more inputs than this 2 lists)

I want to know the biggest prefix of w which is also suffix of w2.

How can I do this only with logic (without importing anything)

CodePudding user response:

I can try and help get you started on this problem, but it sort of sounds like a homework question so I won't give you a complete answer (per these guidelines).

If I were you I'd start with a small case and build up from there. Lets start with:

w = "ab"
w2 = "ba"

The function for this might look like:

def function(w,w2):
    prefix = ""
    # Does the first letter of w equal the last letter of w2?
    if w[0] == w2[-1]:
        prefix  = w[0]
        
    # What about the second letter?
    if w[1] == w2[-2]:
        prefix  = w[1]

    return prefix

Then when you run print(function(w,w2)) you get ab.

This code should work for 2 letter words, but what if the words are longer? This is when we would introduce a loop.

def function(w,w2):
    prefix = ""
    
    for i in range(0, len(w)):
        if w[i] == w2[(i 1)*-1]:
            prefix = w[i]
        else:
            return prefix
            
    return prefix

Hopefully this code will offer a good starting place for you! One issue with what I have written is what if w2 is shorter than w. Then you will get an index error! There are a few ways to solve this, but one way is to make sure that w is always the shorter word. Best of luck, and feel free to DM me if you have other questions.

CodePudding user response:

A simple iterative approach could be:

  1. Start from the longest possible prefix (i.e. all of w), and test it against a w2 suffix of the same length.
  2. If they match, you can return it immediately, since it must be the longest possible match.
  3. If they don't match, shorten it by one, and repeat.
  4. If you never find a match, the answer is an empty string.

In code, this looks like:

>>> def function(w, w2):
...     for i in range(len(w), 0, -1):
...         if w[:i] == w2[-i:]:
...             return w[:i]
...     return ''
...
>>> function("asdfasdf", "qwertyasdf")
'asdf'

The slice operator (w[:i] for a prefix of length i, w2[-i:] for a suffix of length i) gracefully handles mismatched lengths by just giving you a shorter string if i is out of the range of the given string (which means they won't match, so the iteration is forced to continue until the lengths do match).

>>> function("aaaaaba", "ba")
'a'
>>> function("a", "abbbaababaa")
'a'
  • Related