You will be given an array of strings. The words in the array should mesh together where one or more letters at the end of one word will have the same letters (in the same order) as the next word in the array. But, there are times when all the words won't mesh. 

Examples of meshed words:

  "apply" and "plywood"
  
  "apple" and "each"
  
  "behemoth" and "mother"
  
Examples of words that don't mesh:

  "apply" and "playground"
  
  "apple" and "peggy"
  
  "behemoth" and "mathematics"
  

If all the words in the given array mesh together, then your code should return the meshed letters in a string.
You won't know how many letters the meshed words have in common, but it will be at least one.

If all the words don't mesh together, then your code should return `"failed to mesh"`.

Input: An array of strings. There will always be at least two words in the input array.

Output: Either a string of letters that mesh the words together or the string `"failed to mesh"`.


## Examples

#1:

```
["allow", "lowering", "ringmaster", "terror"] --> "lowringter"
```
because:

* the letters `"low"` in the first two words mesh together
* the letters `"ring"` in the second and third word mesh together
* the letters `"ter"` in the third and fourth words mesh together.


#2:

```
["kingdom", "dominator", "notorious", "usual", "allegory"] --> "failed to mesh"
```

Although the words `"dominator"` and `"notorious"` share letters in the same order, the last letters of the first word don't mesh with the first letters of the second word.

Difficulty: EASY
Tags: String algorithms

Fundamentals

Data structures
Skill types: Data structures

Starter code:
def word_mesh(arr):
	

Solutions:
import re

def word_mesh(arr):
	common = re.findall('(.+) (?=\\1)', ' '.join(arr))
	return ''.join(common) if len(common) + 1 == len(arr) else 'failed to mesh'


def word_mesh(arr):
	result = ''
	for (a, b) in zip(arr, arr[1:]):
		while not a.endswith(b):
			b = b[:-1]
		if not b:
			return 'failed to mesh'
		result += b
	return result


def word_mesh(A, z=''):
	for (x, y) in zip(A, A[1:]):
		while not y.startswith(x):
			x = x[1:]
		if x == '':
			return 'failed to mesh'
		z += x
	return z


word_mesh = lambda a, f=lambda c, d, h=[]: h.clear() or [h.extend((d[:i] for i in range(len(c)) if c.endswith(d[:i])))] * 0 or sorted(h, key=len)[-1], g=[]: g.clear() or g.extend((f(x, y) for (x, y) in zip(a, a[1:]))) or (''.join(g) if '' not in g else 'failed to mesh')


def word_mesh(lst):
	meshes = []
	for (w1, w2) in zip(lst, lst[1:]):
		for i in range(min(len(w1), len(w2)), 0, -1):
			if w1[-i:] == w2[:i]:
				meshes.append(w1[-i:])
				break
		else:
			return 'failed to mesh'
	return ''.join(meshes)


def word_mesh(arr):
	overlaps = [max(filter(prev.endswith, (word[:k] for k in range(len(word) + 1)))) for (prev, word) in zip(arr, arr[1:])]
	return ''.join(overlaps) if all(overlaps) else 'failed to mesh'


from itertools import count, takewhile

def word_mesh(arr):
	overlaps = list(takewhile(bool, map(mesher, zip(arr, arr[1:]))))
	return len(overlaps) == len(arr) - 1 and ''.join(overlaps) or 'failed to mesh'

def mesher(pair):
	(a, b) = pair
	nChars = next((i for i in count(min(map(len, pair)), -1) if a.endswith(b[:i])))
	return b[:nChars]


def mesh(a, b):
	for i in range(len(b), 0, -1):
		if a.endswith(b[:i]):
			return b[:i]

def word_mesh(arr):
	try:
		return ''.join((mesh(a, b) for (a, b) in zip(arr, arr[1:])))
	except TypeError:
		return 'failed to mesh'


def word_mesh(arr):
	(re, e, i) = ('', len(arr[0]), 0)
	while e != 0:
		e -= 1
		if e == 0:
			return 'failed to mesh'
		if arr[i][-e:] == arr[i + 1][:e]:
			re += arr[i][-e:]
			e = len(arr[i])
			i += 1
			if i == len(arr) - 1:
				return re