首页 > 代码库 > Group Shifted Strings
Group Shifted Strings
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:
"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"],
A solution is:
[ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"]]
Analyse: keep the diff between each character in the string. Put the strings with same diff in the same vector.
Runtime: 6ms
1 class Solution { 2 public: 3 vector<vector<string>> groupStrings(vector<string>& strings) { 4 unordered_map<string, vector<string> > groups; 5 for (string s : strings) { 6 if (s.size() == 1) { 7 groups["-"].push_back(s); 8 } else { 9 string tempGap;10 for (int i = 1; i < s.size(); i++) {11 if (s[i] > s[i - 1])12 tempGap += to_string(s[i] - s[i - 1]);13 else14 tempGap += to_string(26 + (s[i] - s[i - 1]));15 }16 groups[tempGap].push_back(s);17 }18 }19 20 vector<vector<string> > result;21 for (auto ite = groups.begin(); ite != groups.end(); ite++) {22 vector<string> tempStrings = ite->second;23 result.push_back(vector<string>());24 for (auto s : tempStrings) {25 result.back().push_back(s);26 }27 }28 return result;29 }30 };
Group Shifted Strings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。