# My Concise JAVA Solution

• ``````public class Solution {
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> result = new ArrayList<List<String>>();
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strings) {
int offset = str.charAt(0) - 'a';
String key = "";
for (int i = 0; i < str.length(); i++) {
char c = (char) (str.charAt(i) - offset);
if (c < 'a') {
c += 26;
}
key += c;
}
if (!map.containsKey(key)) {
List<String> list = new ArrayList<String>();
map.put(key, list);
}
}
for (String key : map.keySet()) {
List<String> list = map.get(key);
Collections.sort(list);
}
return result;
}
}``````

• Similar idea, thanks for sharing!

``````public class Solution {
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> result = new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for(String s: strings){
String key = getBitMap(s);
if(!map.containsKey(key))
map.put(key, new ArrayList<String>());
}
for(String key: map.keySet()){
List<String> list = map.get(key);
Collections.sort(list);
}
return result;
}
private String getBitMap(String s){
int[] arr = new int[s.length()];
arr[0] = 0;
for(int i = 1; i < s.length(); i++){
arr[i] = s.charAt(i)-s.charAt(0) < 0?
((s.charAt(i)-s.charAt(0))%26 + 26): (s.charAt(i)-s.charAt(0));
}
return Arrays.toString(arr);
}
``````

}

• I think you should add some tag when you append the numbers, or [12, 1] and [1, 21] will be treated as the same key.

• Nice! Two suggestions: (1) Use a `StringBuilder` instead of `key += c;` (2) Abstract key encoding logic into one function for better readability.

• Just another similar version.

``````    public List<List<String>> groupStrings(String[] ss) {
Map<String, List<String>> map = new HashMap<>();

for(String s: ss){
String key = getTag(s);
List<String> value = map.get(key);
if(value == null){
value = new ArrayList<>();
map.put(key, value);
}

}

List<List<String>> ret = new ArrayList<>();
for(List<String> lst: map.values()){
Collections.sort(lst); // dont forget to sort.
}

return ret;
}

String getTag(String s){
int diff = (int)s.charAt(0) - (int)'a';

StringBuilder sb = new StringBuilder();
for(char c: s.toCharArray())
sb.append((c+26-diff)%26);

return sb.toString();
}``````

• I would use just simple char[] (instead of StringBuilder) - as the length of the string is known in advance. Then construct new String(chars).

``````public List<List<String>> groupStrings(String[] strings) {
List<List<String>> ret = new ArrayList<List<String>>();
HashMap<String, List<String>> map = new HashMap<String, List<String>>();
for(String s : strings) {
String key = "";
for(int i = 1; i < s.length(); i++) {
int offset = s.charAt(i) - s.charAt(i - 1);
key += offset < 0 ? offset + 26 : offset;
}
if(!map.containsKey(key)) map.put(key, new ArrayList<String>());
}
for(List<String> ss : map.values()) {
Collections.sort(ss);
}
return ret;
}``````

• It treats the diff as a char, not a integer.

• ``````public List<List<String>> groupStrings(String[] strings) {
List<List<String>> res = null;
Map<String,List<String>> map = new HashMap<>();

for(String string: strings){
int shift = string.charAt(0) - 'a';
StringBuilder key = new StringBuilder();

for(int i=0;i<string.length();i++){
key.append((char)(string.charAt(i)+26-shift)%26);
}

String k = key.toString();
if(!map.containsKey(k)) map.put(k,new ArrayList<String>());
}
res = new ArrayList<>(map.values());
return res;
}
``````

• if you have empty string, this would not work ,right?

• Ugh, I got asked this question by Google and I did it in O(n^2). Needless to say I didn't proceed to the next round.

• @lekzeey

I am sorry to hear that bro. But most of the solutions appeared in the discussion board are O(N^2).

• @ZZJJ Similar solution. But why do we need to sort the values. I didn't sort but still got AC. Runtime is 7ms.

``````    public List<List<String>> groupStrings(String[] strings) {
Map<String,List<String>> map = new HashMap<String,List<String>>();
for(int i=0;i<strings.length;i++){
String word = shift(strings[i]);
if(!map.containsKey(word)){
map.put(word,new ArrayList<String>());
}
}
return new ArrayList(map.values());
}
public String shift(String word){
if(word==null||word.length()==0)
return word;
char[] chArray = word.toCharArray();
StringBuilder sb = new StringBuilder();
for(int i=0;i<chArray.length-1;i++){
sb.append(((chArray[i+1]-chArray[i])<0?chArray[i+1]-chArray[i]+26:chArray[i+1]-chArray[i])+"");
}
return sb.toString();
}
``````

• What is the time complexity of this solution ?

• @lekzeey I hate to say it, but I think you messed up somewhere else. I don't think this question can be done in O(n) time... my O(n^2) solution beats 98% of python solutions so... how can they expect better? Maybe some other criteria you messed up :/

A side point, I agree @Derek_Han. Sorting is not necessary for this question. Only slows down solution time.

• ``````public class Solution {
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> res = new ArrayList();
int n = strings.length;
Map<Integer, List<String>> map = new HashMap();
boolean[] vis = new boolean[n];

for (int i = 0; i < n; i++) {
if (vis[i]) continue;
vis[i] = true;
List<String> list = new ArrayList();
for (int j = 1; j < n; j++) {
if (vis[j]) continue;
if (isMatch(strings[i], strings[j])) {
vis[j] = true;
}
}
}
return res;
}

private boolean isMatch(String a, String b) {
if (a.length() != b.length()) return false;
if (a.length() == 1) return true;
int len = a.length();
int i = 1;
int degree = (a.charAt(0) - b.charAt(0) + 26) % 26;
while (i < len) {
if (degree != (a.charAt(i) - b.charAt(i) + 26) % 26) return false;
i++;
}
return true;
}
}
``````

• @huaying2 Same as yours except use of char array instead of StringBuilder.
At first, I shift each char by: ch[i] = (char) ('a' + (ch[i] - 'a' + (26 - shift)) % 26); which seems not necessary.
But I think we forget to sort before return, right?

``````    public List<List<String>> groupStrings(String[] strs) {
Map<String, List<String>> group = new HashMap<>();
for (String str : strs) {
char[] c = str.toCharArray();
for (int i = 0, shift = c[0] - 'a'; i < c.length; i++)
c[i] = (char) ((c[i] + 26 - shift) % 26);

String key = String.valueOf(c);
if (!group.containsKey(key))
group.put(key, new ArrayList<>());
}
return new ArrayList<>(group.values());
}
``````

• Actually I wonder the function of `+26` in the `c[i] = (char) ((c[i] + 26 - shift) % 26);` Seems everybody uses it but it can still pass the OJ without adding 26.
Plus, can anyone clarify the workflow of `%` operation here? I think it is for handling situations like 'y'+2->'a', but it's not easily visualizable.

• @OpMaker

In the problem statement, it says Given a list strings which contains only lowercase alphabets.

In this case, `+26` isn't necessary, as `c[i]` is always `> 96`.

But, it'll cause problems if characters are in a wider range.

• A sligth improvement, use addAll() to add collections of values at the end into the result and return, it will be much easier!

``````    public List<List<String>> groupStrings(String[] strings) {
List<List<String>> result = new ArrayList<List<String>>();
Map<String, List<String>> map = new HashMap<String, List<String>>();

for (String s: strings) {
//create key for the string, make first letter into a
if (s.length() == 0) continue;
int offset = s.charAt(0) - 'a';
String key = "";
for (int i = 0; i < s.length(); i++) {
char c = (char) (s.charAt(i) - offset);
if (c < 'a') c += 26; //rotate
key += c; //apend the c
}

if (!map.containsKey(key)) {
map.put(key, new ArrayList<String>());
}