Trie fun
Intuition\nIf a is matching with b, then be is matching with a too. \nSo if we calculate all matches (a,b and b,a)and then divide by 2, we get the result.\n\nTo
# Intuition\nIf a is matching with b, then be is matching with a too. \nSo if we calculate all matches (a,b and b,a)and then divide by 2, we get the result.\n\nTo reduce the branches while searching we can use trie . We can put the original values in the nums in the trie first.\n\nNow during the exploration of the swap values, we can find the matches in the trie that contains original values.\n\n# Approach\n\nUsing the trie is just like a dictionary or hash-table.\n\nWe have just put our matches in the trie/hash-table.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(N)\n\n# Code\n```python3 []\n\nclass Trie:\n    def __init__(self, val):\n        self.val = val\n        self.child = [None]*10\n        self.content = set()\n        self.contentDgts = None\n        self.matches = set()\n        \n    def pushKey(self, dgts, idx):\n        cur = self\n        for x in dgts:\n            if cur.child[x] is None:\n                cur.child[x] = Trie(x)\n            cur = cur.child[x]\n        cur.content.add(idx)\n        cur.contentDgts = dgts\n        \n    def pushPairRecursive(self, dgts, pos, idx, pos1, pos2):\n\n        if pos >= len(dgts):\n            # no more room\n            if len(self.content):\n                self.matches.add(idx)\n            return\n        \n        spos = pos\n        if pos2 is not None:\n            if pos2 == spos:\n                spos = pos1\n                \n        if self.child[dgts[spos]] is not None:\n            self.child[dgts[spos]].pushPairRecursive(dgts,pos+1,idx,pos1, pos2)\n            \n        if pos1 is None:\n            # we can swap pos as pos1, with some pos2\n            for pos2 in range(pos+1,len(dgts)):\n                if self.child[dgts[pos2]] is not None:\n                    self.child[dgts[pos2]].pushPairRecursive(dgts,pos+1,idx,pos, pos2)\n                    \n    def pushPair(self, dgts, idx):\n        cur = self\n        for x in dgts:\n            if cur.child[x] is None:\n                return\n            cur = cur.child[x]\n        cur.matches.add(idx)\n                    \n    def find(self, dgts):\n        cur = self\n        for i,x in enumerate(dgts):\n            if cur.child[x] is None:\n                return None\n            cur = cur.child[x]\n            \n        return cur\n    \n    def dump(self):\n        if len(self.content):\n            print(self.contentDgts,self.matches)\n        for i,x in enumerate(self.child):\n            if x is not None:\n                x.dump()\n                \n    def iterAll(self):\n        stack = [self]\n        while stack:\n            cur = stack.pop()\n            if len(cur.content) and len(cur.matches):\n                yield cur\n            for x in cur.child:\n                if x is not None:\n                    stack.append(x)\n                \nclass Solution:\n    def countPairs(self, nums: List[int]) -> int:\n        \n\n        def calcDigits(given, givenSz = 0):\n            ret = []\n            while given:\n                given,digit = divmod(given,10)\n                ret.append(digit)\n                \n            while len(ret) < givenSz:\n                ret.append(0)\n            return ret\n\n        biggest = max(nums)\n        SZ = len(calcDigits(biggest))\n\n        dgtList = [None]*len(nums)\n        tri = Trie(None)\n        for i,x in enumerate(nums):\n            digits = calcDigits(x, SZ)\n            dgtList[i] = digits\n            tri.pushKey(digits, i)\n            \n        for i,x in enumerate(nums):\n            digits = dgtList[i]\n            tri.pushPair(digits,i) \n            for ii in range(SZ):\n                for jj in range(ii+1,SZ):\n                    if digits[ii] != digits[jj]:\n                        digits2 = digits[:]\n                        digits2[ii] = digits[jj]\n                        digits2[jj] = digits[ii]\n                        tri.pushPairRecursive(digits2,0,i,None,None) \n        \n        #tri.dump()\n        result = 0\n        for node in tri.iterAll():\n            result += (len(node.matches)-1)*(len(node.content))\n            #result += (vv*(vv-1))>>1\n            \n        return result>>1\n```
['Python3']