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$

Difficulty: interview

Starter code:

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")

# Solution link: https://leetcode.com/problems/verbal-arithmetic-puzzle/discuss/939496/Python-Optimizations-to-beat-TLE-Top-Down-DP-(93)


#dt = {} for i in x: dt[i] = dt.get(i,0)+1
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

    # 1. Check the lengths of each word and result
    longest_word = len(max(words, key = len))
    if (len(result) < longest_word) or (len(result) > longest_word + 1):
        return False

    # 2. Check if result is in words
    if result in words:
        return len(words) < 3 and all(word == result or len(word) == 1 for word in words)

    # 3. Leading letters cannot be zero unless the length of the word is 1
    not_zero = set((word[0] for word in words if len(word) > 1))
    if len(result) > 1: not_zero.add(result[0])

    # 4. Set of all letters
    chars = set(result + ''.join(words))

    # 5. Letters in words add to the total
    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)

    # 6. And letters in result subtract from the total
    for i,char in enumerate(reversed(result)):
        mult[char] -= 10**i
        groups[i].add(char)

    # 7. Letters that add and subtract the same amount can be any number, so ignore them.
    chars = {char for char in chars if mult[char]}
    for g in groups:
        groups[g] = groups[g].intersection(chars)
    chars = list(chars)

    # 8. All letters that occur later in the word may affect letters ealrier in the word
    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]))

    # 9. Once a number has been assigned to all the letters in a group
    #    the digit in total at position 10**i must be zero for a solution to exist
    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")