Problem statement

https://leetcode.com/problems/verbal-arithmetic-puzzle/

Solution

Not very nice problem: we need to do dfs with some pruning. Here I use dfs(words, free), where words are partially solved puzzle and free are digits which are still available. Each time we check for each word how many last letters we already allocated and check if we have conflict modulo 10**l_min. If we have it or any word starts with zero, but not equal to zero, return. Then we check if l_min == 10 it means that all letters already replaced with digits and if M == 0, it means that we have solution.

Imagine, that we have so far [###12, ###34, ####6], where the last one is answer. Then what we need to choose is the letter before 6 and try to allocate any digit. (in fact here we can directly allocate 5, but it is more difficult to code)

Complexity

Time complexity potentially is O(10!), but due to pruning it passed. In python it works quite slow and can be made 10 times faster, but I do not like this problem so I do not want to do it.

Code

class Solution:
    def isSolvable(self, words, result):
        def last_d(s):
            if s.isdigit(): return 10  #means word is fully covered
            for i in range(len(s)-1, -1, -1):
                if not s[i].isdigit(): break
            return len(s) - i - 1
        
        def dfs(words, free):
            if self.Found: return
            lasts = [last_d(w) for w in words]
            l_min = min(lasts)
            ends = [int(w[-l_min:]) if l_min else 0 for w in words]
            M = sum(ends) - 2*ends[-1]
            
            if M % (10**l_min) != 0 or any(w[0] == "0" and w != "0" for w in words):
                return
            
            if l_min == 10 and M == 0:
                self.Found = True
                return
            
            l_ind = lasts.index(l_min)
            symb = words[l_ind][-l_min - 1]
            
            for num in free:
                words2, free2 = words[:], free.copy()
                for i, w in enumerate(words2):
                    words2[i] = w.replace(symb, str(num))
                free2.remove(num)
                dfs(words2, free2)
        
        self.Found = False
        dfs(words + [result], set(range(10)))
        return self.Found