Two friends David and Rojer were preparing for their weekly class-test.
The are preparing for the math test, but because of continuously adding big integers and solving equations they got exhausted. They decided to take break and play a game. They play a game which will help them in both(for having fun and will also help to prepare for math test).
There are N words and they have to find RESULT with the help of these words (just like they have N integers and they have to find integer RESULT=sum of N integers) . Since they are playing this game for the first time! They are not too good in this. Help them in finding weather their RESULT is correct or not.   
NOTE:- Total number of unique characters in N words are not greater than 10. All input words and RESULT are in UPPER-CASE only!
Refer Here for how to add numbers : https://en.wikipedia.org/wiki/Verbal_arithmetic

-----Input:-----
- First line consist of an integer N (total number of words).
- Next N line contains words with which they have to find RESULT.
- Last line consist of the RESULT they found.

-----Output:-----
If RESULT is correct print true else print false.

-----Sample Input:-----
3

THIS

IS

TOO

FUNNY  

-----Sample Output:-----
true

-----Constraints-----
- $2 \leq N \leq 10$
- $1 \leq Length of The word \leq 10$
- $1 \leq Length of The Result \leq 11$

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def isSolvable(W, R):
	(LW, LR, F, ML, AW, V, LMap) = (len(W), len(R), set([w[0] for w in W + [R]]), max(map(len, W + [R])), W + [R], set(), {})
	if LR < ML:
		return False

	def dfs(d, i, c):
		if d == ML:
			return c == 0
		if i == len(W) + 1:
			s = sum((LMap[w[-d - 1]] if d < len(w) else 0 for w in W)) + c
			return dfs(d + 1, 0, s // 10) if s % 10 == LMap[R[-d - 1]] else False
		if i < LW and d >= len(W[i]):
			return dfs(d, i + 1, c)
		ch = AW[i][-d - 1]
		if ch in LMap:
			return dfs(d, i + 1, c)
		for x in range(ch in F, 10):
			if x not in V:
				(LMap[ch], _) = (x, V.add(x))
				if dfs(d, i + 1, c):
					return True
				V.remove(LMap.pop(ch))
	return dfs(0, 0, 0)
n = int(input())
W = []
for i in range(n):
	W.append(str(input()))
R = input()
a = isSolvable(W, R)
if a == True:
	print('true')
else:
	print('false')


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
import functools, collections

def isSolvable(words, result):

	@functools.lru_cache(None)
	def helper(i, total, nums):
		if i == len(chars):
			return total == 0
		if i - 1 in checkpoints:
			t = str(abs(total))[::-1]
			for j in checkpoints[i - 1]:
				if j < len(t) and t[j] != '0':
					return False
		for j in range(len(nums)):
			if nums[j] == 0 and chars[i] not in not_zero and helper(i + 1, total, nums[:j] + nums[j + 1:]):
				return True
			elif nums[j] != 0 and helper(i + 1, total + nums[j] * mult[chars[i]], nums[:j] + nums[j + 1:]):
				return True
		return False
	longest_word = len(max(words, key=len))
	if len(result) < longest_word or len(result) > longest_word + 1:
		return False
	if result in words:
		return len(words) < 3 and all((word == result or len(word) == 1 for word in words))
	not_zero = set((word[0] for word in words if len(word) > 1))
	if len(result) > 1:
		not_zero.add(result[0])
	chars = set(result + ''.join(words))
	mult = {char: 0 for char in chars}
	groups = collections.defaultdict(set)
	for word in words:
		for (i, char) in enumerate(reversed(word)):
			mult[char] += 10 ** i
			groups[i].add(char)
	for (i, char) in enumerate(reversed(result)):
		mult[char] -= 10 ** i
		groups[i].add(char)
	chars = {char for char in chars if mult[char]}
	for g in groups:
		groups[g] = groups[g].intersection(chars)
	chars = list(chars)
	for g in range(1, len(groups)):
		groups[g] |= groups[g - 1]
	chars.sort(key=lambda c: min((g for g in range(len(groups)) if c in groups[g])))
	checkpoints = collections.defaultdict(list)
	seen = set()
	checked = set()
	for (i, char) in enumerate(chars):
		seen.add(char)
		for g in groups:
			if g not in checked and groups[g].issubset(seen):
				checked.add(g)
				checkpoints[i].append(g)
	return helper(0, 0, tuple(range(10)))
n = inp()
x = [input().strip() for i in range(n)]
y = input().strip()
ans = isSolvable(x, y)
if ans:
	print('true')
else:
	print('false')