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:
Return:
["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.
A:
class Solution { public: vector<vector<string>> groupStrings(vector<string>& strings) { unordered_map<string, vector<string>> M; for(auto &s:strings){ // represent each string with their char difference string tmp=""; for(int i =1;i<s.length();i++){ tmp+= to_string( (26 + s[i]-s[i-1]) %26); } M[tmp].push_back(s); } vector<vector<string>> res; auto iter = M.begin(); while(iter!= M.end()){ res.push_back(iter->second); iter++; } return res; } };
1: 一个整数 -1 % 26, 的结果为 -1 , 因此计算新的char的时候, 得加上26
一开始犯了糊涂, az, za 的difference 的结果是不一样的。
No comments:
Post a Comment