博文中会简要介绍Leetcode P0249题目分析及解题思路。
“Group Shifted Strings”是一道中等难度的题目。这道题的关键在于如何对shifting这个特征实现有效的编码。
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 non-empty strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
Example:
Input: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"], Output: [ ["abc","bcd","xyz"], ["az","ba"], ["acef"], ["a","z"] ]
譬如abc和bcd，这两个字符串属于同一个类别，仔细观察不难发现，字符串中相邻的两个字母，右边的字母序比左边的字母序大1，也就是说含有同样特征的且长度相同的字符串属于同一类别。再譬如az和ba这两个字符串，可以看作相邻两个字母，右边的字母序比左边的字母序小1，但也可以看作右边的字母序比左边的字母序大25，而使用后者编码会更为简单，也能和前一个例子归并成统一的编码方式。
总的来说，将这种相邻字母的字母序间差值作为不同组的特征，相当于对字符串进行了一次编码，而具有相同编码的字符串自然也就属于同一类别。
以下是Java的题解代码实现。
class Solution {
public List<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> groups = new HashMap<>();
for (String str: strings) {
String encoded = this.encode(str);
if (!groups.containsKey(encoded)) {
groups.put(encoded, new ArrayList<>());
}
groups.get(encoded).add(str);
}
List<List<String>> ret = new ArrayList<>();
for (Map.Entry<String, List<String>> entry: groups.entrySet()) {
ret.add(entry.getValue());
}
return ret;
}
private String encode(String raw) {
StringBuilder builder = new StringBuilder("0#");
for (int idx=1; idx<raw.length(); ++idx) {
int offset = this.calculate(raw.charAt(idx-1), raw.charAt(idx));
builder.append(offset);
builder.append("#");
}
return builder.toString();
}
private int calculate(int p, int q) {
return (q+26-p)%26;
}
}
以下是C++的题解代码实现。
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
unordered_map<string, vector<string>> groups;
for (string str: strings) {
string encoded = _Encode(str);
groups[encoded].push_back(str);
}
vector<vector<string>> ret;
for (auto entry: groups) {
ret.push_back(entry.second);
}
return ret;
}
private:
string _Encode(string raw) {
string builder("#");
for (int idx=1; idx<raw.length(); ++idx) {
int offset = _Calculate(raw[idx-1], raw[idx]);
builder += to_string(offset);
builder += "#";
}
return builder;
}
int _Calculate(int p, int q) {
return (q+26-p)%26;
}
};