Leetcode 49 : Group Anagrams Solution

Problem Statement could be found @https://leetcode.com/problems/anagrams/

Approach -
1. To put all anagrams of a string together we need some way to bucket, so that all anagrams land up in same bucket
2. To get to bucket we can use integer hashing but problem there would be collision.
3. To avoid collision we are using a string key (acting as a hash). For each string we take the smallest string lexicographic-ally which can be created from it as the hash key and store the all strings which have occurred so far.

Following is the code snippet

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
          map<string, vector<string>> m;
         
          for (int i=0; i<strs.size();i++){
             
              string s = strs[i];
              sort(s.begin(), s.end());
              vector<string> v;
              if(m.count(s) >0){
                  v = m[s];
              }
              v.push_back(strs[i]);
              m[s]=v;
          }
         
          vector<vector<string>> retvec;
          for(auto a=m.begin(); a!= m.end(); a++){
              retvec.push_back(a->second);
          }
          return retvec;
    }
};

Leetcode 39 : Combination Sum solution

Problem Statement could be found @ https://leetcode.com/problems/combination-sum/

Approach - Let us consider the example given in  problem statement itself.

input - [2, 3, 6, 7]
target - 7

Here, we have to consider each element multiple times so we will first start with 2
So, first we pick 2,2,2,2 then sum becomes 8, so noway picking 2 or any other number from input another time would give us desired target. And Hence we need to go back

Now, when we go back we have 2,2,2 and next number we pick up is 3.Again sum is 9,so we need to go back. Similarly, we pick  6 & 7 next. This step could have been optimized to short circuit at 2,2,2,2 itself, but here I'm not doing that much optimization.

Next we go back and have 2,2. Next number picked up is 3. So the sum becomes 7 which is desired . Hence we store it in output.

Points to consider
1. The input array may not be sorted so it is better to sort it initially
2. Since numbers are not negative, we can leverage on total sum being greater than target to stop
3. At every step we are almost doing the same step hence recursion can be used and point 2 can be used as terminating condition for recursion


Code Snippet-

class Solution {
    vector<vector<int>> retvec;
    vector<int> val;
    int target;
public:
void helper(int index, int sum, vector<int> &v){
   
    if (sum > target){
        return;
    }
   
    if ( sum == target){
        retvec.push_back(v);
        return;
    }
   
    for (int i=index;i<val.size();i++){
        v.push_back(val[i]);
        helper(i, sum+val [i],v);
        v.pop_back();
    }
}
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        this->target = target;
       
        val = candidates;
        sort(val.begin(), val.end());
        vector<int> v;
        helper(0,0,v);
        return retvec;
    }
};

Leetcode17 : Letter Combinations of a Phone Number Solution

Problem statement could be found @https://leetcode.com/problems/letter-combinations-of-a-phone-number/

This code is very simple and just works on the recursion.

Approach -
1. Create a mapping of digits and corresponding characters
2. For each digit given in the input,  pick  one character at a time from the mapping and then move to next digit.

Code snippet -

class Solution {
public:
    map<char, string> dict;
    string digits;
    vector<string > retvec;
    void init(){
        dict[2] = "abc";
        dict[3] = "def";
        dict[4] = "ghi";
        dict[5] = "jkl";
        dict[6] = "mno";
        dict[7] = "pqrs";
        dict[8] = "tuv";
        dict[9] = "wxyz";
    }
    void helper( int index, string s){
        if ( index >= digits.length()){
            retvec.push_back(s);
            return ;
        }
        string x = dict[digits[index]-'0'];
        for ( int i=0;i<x.length();i++){
            helper(index+1, s+ x[i]);
           
        }
    }
    vector<string> letterCombinations(string digits) {
        this-> digits = digits;
        if ( digits.length() == 0){
            return retvec;
        }
        init();
        string s;
        helper(0, s);
        return retvec;
    }
};