Group Shifted Strings Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Bloomberg Facebook Google Uber
WixViews 1843

Problem Statement

Group Shifted Strings Leetcode Solution – We can shift a string by shifting each of its letters to its successive letter.

  • For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

  • For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

Example 1:

Input:

 strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

Output:

 [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Example 2:

Input:

 strings = ["a"]

Output:

 [["a"]]

Constraints:

  • 1 <= strings.length <= 200
  • 1 <= strings[i].length <= 50
  • strings[i] consists of lowercase English letters.

Approach

Idea:

  1. The basic idea of this problem is to set a key for each string
  2. how do we set a key for any string?
  3. we can say that if 2 strings belong to the same group then distance b/w adjacent characters in both remains the same
  4. for example bc and xyz.
  5. if s[i] – s[i – 1] is negative, we need to do (dis+26)%26 to it to make it positive and give the correct result
  6. we make an unordered map <string, vector<string> >    we store the string corresponding to the key in a hashmap.

Group Shifted Strings Leetcode Solution

Code

C++ Program of  Group Shifted Strings

class Solution {
public:
    vector<vector<string>> groupStrings(vector<string>& strings) {

        unordered_map<string,vector<string> > mp;
        
        for(int i=0;i<strings.size();i++)
        {
            string key="-";
            string s=strings[i];
            
            for(int j=1;j<s.length();j++)
            {
               int dis=(s[j]-s[j-1]+26)%26;
               key.append(to_string(dis));
               key+='-';
            }
            mp[key].push_back(s);
        }
    
        vector<vector<string> > ans;
        for(auto itr:mp)
        {
            ans.push_back(itr.second);
        }  
        return ans;  
    }
};

Java  Program of  Group Shifted Strings

class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        Map<String,List<String>> mp = new HashMap<>();
        for(int i=0;i<strings.length;i++)
        {    
            String s=strings[i];
            StringBuilder key  = new StringBuilder();
            key.append("-");
            for(int j = 1; j < s.length();j++)
            {
                int dis= (s.charAt(j) - s.charAt(j-1) + 26) % 26;
                // in case [0,1,11] [0,11,1], so i add "." to key.
                key.append(Integer.toString(dis));
                key.append("-");
               
           }
            String k = key.toString();
            if(!mp.containsKey(k)){
                List<String> value = new ArrayList<>();
                mp.put(k,value);
            }
            mp.get(k).add(s);
        }     
        List<List<String>> ans = new ArrayList<>();
        for(String key: mp.keySet()){
           ans.add(mp.get(key));
        }
        return ans;
    }
}

Complexity Analysis for Group Shifted Strings Leetcode Solution

Time Complexity

The time complexity of the above code is O(n*m)  where n is the size of the strings array and m is the   length of  string whose length is maximum in the array

Space Complexity

The space complexity of the above code is O(n) because we are using a hash map to store the groups.

Translate »