C++ DFS Solution
Approach\n Describe your approach to solving the problem. \nBasically, dfs the possible swap of each number and increase the count of each visited number. \n\n#
# Approach\n<!-- Describe your approach to solving the problem. -->\nBasically, dfs the possible swap of each number and increase the count of each visited number. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(7C2 * 7C2 * n)$$\n\nEach number can expand to 7C2 number(coz num < 1e7), and we at most swap twice. so it takes O(7C2 * 7C2) to explore each possible swap of a number\n\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$ \n\n# Code\n```cpp []\nclass Solution {\nprivate:\n    void dfs(vector<int>& digits, set<int>& visited, int x, int step){\n        visited.insert(x);\n        if(step==2){\n            return;\n        }\n        for(int i = 0; i < digits.size(); ++i){\n            for(int j = i+1; j < digits.size(); ++j){\n                if(digits[i]==digits[j]) continue;\n                int x_ = x + (digits[j]-digits[i])*div[i] + (digits[i]-digits[j])*div[j];\n                swap(digits[i], digits[j]);\n                dfs(digits, visited, x_, step+1);\n                swap(digits[i], digits[j]);\n            }\n        }\n    }\nprivate:\n    vector<int> query_digits(int x){\n        vector<int> v(MAX_D, 0);\n        for(int i = 0; i < MAX_D; ++i){\n            v[i] = x%10;\n            x/=10;\n        }\n        return v;\n    }\n    \n    void construct(){\n        div = vector<int>(MAX_D, 1);\n        for(int i = 1; i < div.size(); ++i){\n            div[i] = div[i-1] * 10;\n        }\n    }\n    \n    void visit(int x){\n        vector<int> digits = query_digits(x);\n        set<int> visited;\n        dfs(digits, visited, x, 0);\n        for(auto v : visited){\n            counts[v]++;\n        }\n    }\n    \npublic:\n    int countPairs(vector<int>& nums) {\n        construct();\n        int ret = 0;\n        for(auto x: nums){\n            ret += counts[x];\n            visit(x);\n        }\n        return ret;\n    }\nprivate:\nconst int MAX_D = 7;\nvector<int> div;\nunordered_map<int, int> counts;\n};\n```
['C++']