[C++] 2 Solutions || Permutation and Combination Approach || Brute Force
Intuition - Brute Force\n- The first apprach is a simple one. You just find all the combinations of the strings, concatenate them and thereafter find whether th
# Intuition - Brute Force\n- The first apprach is a simple one. You just find all the combinations of the strings, concatenate them and thereafter find whether the concatenated string matches the `target` string.\n- Had this been the ONLY solution to the problem, this problem would have been marked as an easy problem. However, there\'s another optimization to the problem which is given below...\n\n# Intuition - Optimized Permutation and Combination Approach\n- Here, rather than concatenating all the given strings, we break the `target` string into substrings and find whether these 2 strings are present in the pool of strings given to us in the `nums` vector. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Since we know that we\'re going to perform searching in `nums`, we create another `unordered_map` which contains these given strings as well as their frequencies in `nums`.\n- Now, for every pair of substrins we can create using the `target`, we firstly check whether both of them exists in the pool of strings given to us. If yes, we perform the steps below.\n- If the 2 substrings not equal, we find the number of occurences of both of these substrings, multiply their occurences and thereafter add the result to an `ans` variable.\n- If the 2 substrings are equal, we\'d do the same, rather we\'ll subtract 1 from either of the frequencies and thereafter add the result in the `ans` variable.\n\n# Explanation\n- The optimized approach is based on Permutation and Combination.\n- Imagine `N` number of things are to be paired with `M` number of things. The total number of ways in which you can do that is `N x M`. More specifically, it\'s $${N\\choose 1}$$ x $${M\\choose 1}$$.\n- Similarly, if you have `N` number of things and you want to pair them with one another, you can do that in `N x (N - 1)` ways. More specifically, it\'s $${N\\choose 1}$$ x $${N - 1\\choose 1}$$ (Since 1 `N` is already chosen).\n\n(Here, $${N\\choose R}$$ means superscript N, C, subscript R, which means the number of ways of choosing R different things out of N things)\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code - Brute Force \n```\nclass Solution {\npublic:\n    int numOfPairs(vector<string>& nums, string target) {\n        int ans = 0;\n\n        for(int i = 0; i < nums.size(); i++){\n            for(int j = 0; j < nums.size(); j++){\n                if(i != j && nums[i] + nums[j] == target){\n                    ans++;\n                }\n            }\n        }\n\n        return ans;\n    }\n};\n```\n\n# Code - Optimized Approach\n```\nclass Solution {\npublic:\n    int numOfPairs(vector<string>& nums, string target) {\n        unordered_map<string  , int> allNums;\n        for(string i : nums){\n            allNums[i]++;\n        }\n\n        int ans = 0;\n\n        for(int i = 1; i < target.length(); i++){\n            string s1 = target.substr(0 , i);\n            string s2 = target.substr(i , target.length() - i);\n\n            if(allNums.find(s1) != allNums.end() && allNums.find(s2) != allNums.end()){\n                if(s1 != s2){\n                    ans += (allNums[s1] * allNums[s2]);\n                } else {\n                    ans += (allNums[s1] * (allNums[s2] - 1));\n                }\n            }\n            \n        }\n\n        return ans;\n    }\n};\n```\n\n# Note\nI\'m still learning and there maybe a solution which is better than mine. In a case like such, I\'ll be obliged to discuss in the comment section below. \n\nI wish we all land up to the place where we\'re dreaming of. The goal is to never give up for what\'s right and not focusing on the people who want you to stop from doing that despite all odds.
['Hash Table', 'String', 'C++']