LeetCode: Group Shifted Strings | CrazyEgg
Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
Note: For the return value, each inner list’s elements must follow the lexicographic order.
X.
https://discuss.leetcode.com/topic/20722/my-concise-java-solution/
https://discuss.leetcode.com/topic/37916/5ms-java-solution
Two suggestions: (1) Use a
http://www.chenguanghe.com/group-shifted-strings/
可以看出, 当一个string的字符之间的距离决定了shift后的string. 所以对字符之间的距离进行记录, 当做key, 就可以找到. 这里先取一下string首字母当做offset, 然后算距离. 最后记录在一个key(string)中.
https://leetcode.com/discuss/64979/simple-solution-in-java-with-detailed-explaination
public List<List<String>> groupStrings(String[] strings) { List<List<String>> res = new ArrayList<List<String>>(); HashMap<List<Integer>, List<String>> map = new HashMap<List<Integer>, List<String>>(); for(int i=0; i<strings.length; i++) { List<Integer> curKey = new ArrayList<Integer>(); String str = strings[i]; int length = str.length(); curKey.add(length); for(int j=1; j<length; j++) { int offset = str.charAt(j) - str.charAt(j-1); int val = offset > 0 ? offset : 26 + offset; curKey.add(val); } if (map.containsKey(curKey)) { List<String> tmp = map.get(curKey); tmp.add(str); } else { List<String> tmp = new ArrayList<String>(); tmp.add(str); res.add(tmp); map.put(curKey, tmp); } } for(int i=0; i<res.size(); i++) { List<String> tmp = res.get(i); Collections.sort(tmp); } return res; }
https://discuss.leetcode.com/topic/20755/1-4-lines-in-java
public List<List<String>> groupStrings(String[] strings) { return new ArrayList(Stream.of(strings).sorted().collect(Collectors.groupingBy( s -> s.chars().mapToObj(c -> (c - s.charAt(0) + 26) % 26) .collect(Collectors.toList()) )).values()); }
Read full article from LeetCode: Group Shifted Strings | CrazyEgg
Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
1
| "abc" -> "bcd" -> ... -> "xyz"
|
Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
For example.
given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], Return:[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
Note: For the return value, each inner list’s elements must follow the lexicographic order.
X.
https://discuss.leetcode.com/topic/20722/my-concise-java-solution/
https://discuss.leetcode.com/topic/37916/5ms-java-solution
Two suggestions: (1) Use a
StringBuilder instead of key += c; (2) Abstract key encoding logic into one function for better readability. 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);
}
value.add(s);
}
List<List<String>> ret = new ArrayList<>();
for(List<String> lst: map.values()){
Collections.sort(lst); // dont forget to sort.
ret.add(lst);
}
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();
}string getDiffString(string str){ string shift = ""; for (int i = 1; i < str.length(); i++) { int dif = str[i] - str[i-1]; if (dif < 0) dif += ALPHA; // Representing the difference as char shift += (dif + 'a'); } // This string will be 1 less length than str return shift;}// Method for grouping shifted stringvoid groupShiftedString(string str[], int n){ // map for storing indices of string which are // in same group map< string, vector<int> > groupMap; for (int i = 0; i < n; i++) { string diffStr = getDiffString(str[i]); groupMap[diffStr].push_back(i); } // iterating through map to print group for (auto it=groupMap.begin(); it!=groupMap.end(); it++) { vector<int> v = it->second; for (int i = 0; i < v.size(); i++) cout << str[v[i]] << " "; cout << endl; }}http://www.chenguanghe.com/group-shifted-strings/
可以看出, 当一个string的字符之间的距离决定了shift后的string. 所以对字符之间的距离进行记录, 当做key, 就可以找到. 这里先取一下string首字母当做offset, 然后算距离. 最后记录在一个key(string)中.
public List<List<String>> groupStrings(String[] strings) {
List<List<String>> res = new ArrayList<List<String>>();
HashMap<String, List<String>> maps = new HashMap<>();
for(int i = 0 ; i < strings.length; i++) {
String key = "";
int offset = strings[i].charAt(0) - 'a';
for(int j = 1; j < strings[i].length(); j++) {
key+= (strings[i].charAt(j) - offset + 26) % 26;
}
if(!maps.containsKey(key))
maps.put(key,new ArrayList<>());
maps.get(key).add(strings[i]);
}
for(List<String> list : maps.values()){
Collections.sort(list);
res.add(list);
}
return res;
}
http://buttercola.blogspot.com/2015/08/leetcode-group-shifted-strings.html
The problem looks quite like the grouping anagrams. So the idea is the same: for each string, find out its "original" format, and check if the hash map contains this original string. If yes, put into the map.
==> It's better to first put each string to its group, then sort each group.
https://leetcode.com/discuss/50557/4ms-easy-c-solution-with-explanations
The problem looks quite like the grouping anagrams. So the idea is the same: for each string, find out its "original" format, and check if the hash map contains this original string. If yes, put into the map.
==> It's better to first put each string to its group, then sort each group.
public class Solution { public List<List<String>> groupStrings(String[] strings) { List<List<String>> result = new ArrayList<List<String>>(); if (strings == null || strings.length == 0) { return result; } Arrays.sort(strings, new LexComparator()); Map<String, List<String>> map = new HashMap<String, List<String>>(); for (String s : strings) { StringBuffer sb = new StringBuffer(); int distance = Character.getNumericValue(s.charAt(0)) - 'a'; for (int i = 0; i < s.length(); i++) { int val = Character.getNumericValue(s.charAt(i)) - distance; val = val < 'a' ? val + 26 : val; char ori = (char) val; sb.append(ori); } String original = sb.toString(); if (map.containsKey(original)) { List<String> list = map.get(original); list.add(s); map.put(original, list); } else { List<String> list = new ArrayList<String>(); list.add(s); map.put(original, list); } } // Iterate the map Iterator it = map.entrySet().iterator(); while (it.hasNext()) { Map.Entry pair = (Map.Entry) it.next(); result.add((List<String>) pair.getValue()); } return result; } private class LexComparator implements Comparator<String> { @Override public int compare(String a, String b) { if (a.length() != b.length()) { return a.length() - b.length(); } for (int i = 0; i < a.length(); i++) { if (a.charAt(i) != b.charAt(i)) { return a.charAt(i) - b.charAt(i); } } return 0; } }}
this manner is adopted: for a string
s of length n, we encode its shifting feature as "s[1] - s[0], s[2] - s[1], ..., s[n - 1] - s[n - 2],".
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string> > mp;
for (string s : strings)
mp[shift(s)].push_back(s);
vector<vector<string> > groups;
for (auto m : mp) {
vector<string> group = m.second;
sort(group.begin(), group.end());
groups.push_back(group);
}
return groups;
}
private:
string shift(string& s) {
string t;
int n = s.length();
for (int i = 1; i < n; i++) {
int diff = s[i] - s[i - 1];
if (diff < 0) diff += 26;
t += 'a' + diff + ',';
}
return t;
}
public List<List<String>> groupStrings(String[] strings) { assert strings != null : "null array"; List<List<String>> result = new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for (String s : strings) { String code = getFeatureCode(s); List<String> val; if (!map.containsKey(code)) { val = new ArrayList<>(); } else { val = map.get(code); } val.add(s); map.put(code, val); } for (String key : map.keySet()) { List<String> val = map.get(key); Collections.sort(val); result.add(val); } return result; } private String getFeatureCode(String s) { StringBuilder sb = new StringBuilder(); sb.append("#"); for (int i = 1; i < s.length(); i++) { int tmp = ((s.charAt(i) - s.charAt(i - 1)) + 26) % 26; sb.append(tmp).append("#"); } return sb.toString(); }
https://leetcode.com/discuss/64979/simple-solution-in-java-with-detailed-explaination
public List<List<String>> groupStrings(String[] strings) { List<List<String>> res = new ArrayList<List<String>>(); HashMap<List<Integer>, List<String>> map = new HashMap<List<Integer>, List<String>>(); for(int i=0; i<strings.length; i++) { List<Integer> curKey = new ArrayList<Integer>(); String str = strings[i]; int length = str.length(); curKey.add(length); for(int j=1; j<length; j++) { int offset = str.charAt(j) - str.charAt(j-1); int val = offset > 0 ? offset : 26 + offset; curKey.add(val); } if (map.containsKey(curKey)) { List<String> tmp = map.get(curKey); tmp.add(str); } else { List<String> tmp = new ArrayList<String>(); tmp.add(str); res.add(tmp); map.put(curKey, tmp); } } for(int i=0; i<res.size(); i++) { List<String> tmp = res.get(i); Collections.sort(tmp); } return res; }
Nice! Two suggestions: (1) Use a
StringBuilder instead of key += c; (2) Abstract key encoding logic into one function for better readability.public List<List<String>> groupStrings(String[] strings) { return new ArrayList(Stream.of(strings).sorted().collect(Collectors.groupingBy( s -> s.chars().mapToObj(c -> (c - s.charAt(0) + 26) % 26) .collect(Collectors.toList()) )).values()); }
Read full article from LeetCode: Group Shifted Strings | CrazyEgg
