class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
}
};
249. 移位字符串分组
给定一个字符串，对该字符串可以进行 “移位” 的操作，也就是将字符串中每个字母都变为其在字母表中后续的字母，比如："abc" -> "bcd"。这样，我们可以持续进行 “移位” 操作，从而生成如下移位序列：
"abc" -> "bcd" -> ... -> "xyz"
给定一个包含仅小写字母字符串的列表，将该列表中所有满足 “移位” 操作规律的组合进行分组并返回。
示例：
输入：["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
输出：
[
["abc","bcd","xyz"],
["az","ba"],
["acef"],
["a","z"]
]
解释：可以认为字母表首尾相接，所以 'z' 的后续为 'a'，所以 ["az","ba"] 也满足 “移位” 操作规律。
相似题目
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.9 MB, 提交时间: 2023-10-21 23:19:29
import "strconv"
func toKey(v string) string {
key := []string{}
for i := 0; i < len(v); i++ {
t := (v[i] - v[0] + 26) % 26
key = append(key, strconv.Itoa(int(t)))
}
return strings.Join(key, ".")
}
func groupStrings(strings []string) [][]string {
m := make(map[string][]string)
for _, v := range strings {
m[toKey(v)] = append(m[toKey(v)], v)
}
ans := [][]string{}
for _, v := range m {
ans = append(ans, v)
}
return ans
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2023-10-21 23:19:10
func groupStrings(strings []string) [][]string {
sort.Strings(strings)
ret := [][]string{}
for i := 0; i < len(strings); i++ {
str := strings[i]
find := false
for j := 0; j < len(ret); j++ {
if len(ret[j][0]) != len(str) {
continue
}
add := int(str[0] - ret[j][0][0])
same := 1
for k := 1; k < len(str); k++ {
if int((str[k] - ret[j][0][k]) + 26)%26 == add { // 计算差值是否相等
same++
} else {
break
}
}
if same == len(str) { // 需要所有差值都相等
ret[j] = append(ret[j], str)
find = true
}
}
if !find {
ret = append(ret, []string{str}) // 没有同组的，新增一个组
}
}
return ret
}
python3 解法, 执行用时: 52 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-21 23:18:43
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]]:
# 字符串之间可以移位得到必然是每一位距离差对应一致的时候
def hashCounter(string):
return tuple(((ord(string[i]) - ord(string[i-1])) % 26) for i in range(1 , len(string))) if len(string) > 1 else 0
ans = defaultdict(list)
for s in strings:
ans[hashCounter(s)].append(s)
return list(ans.values())
cpp 解法, 执行用时: 4 ms, 内存消耗: 8.2 MB, 提交时间: 2023-10-21 23:18:28
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string>> vec2;
unordered_map<string, int> hashmap;
int index = 0;
for (auto key : strings) {
string ss(key);
if (ss[0] != 'a') {
for (int i = 1; i < ss.length(); i++)
ss[i] = (ss[i]- ss[0] + 26) % 26 + 'a';
ss[0] = 'a';
}
if (hashmap.count(ss) > 0) {
vec2[hashmap[ss]].push_back(key);
continue;
}
hashmap[ss] = index++;
vec2.push_back({key});
}
return vec2;
}
};
java 解法, 执行用时: 7 ms, 内存消耗: 41.6 MB, 提交时间: 2023-10-21 23:18:03
class Solution {
public List<List<String>> groupStrings(String[] strings) {
if (strings == null || strings.length == 0) return new ArrayList<>();
Map<String, List<String>> map = new HashMap<>();
for (String str : strings) {
StringBuilder sb = new StringBuilder();
for (char c : str.toCharArray()) {
sb.append("#");
int shift = (c - str.charAt(0) + 26) % 26;
sb.append(shift);
}
String key = sb.toString();
System.out.println(key);
if (!map.containsKey(key)) map.put(key, new ArrayList<String>());
map.get(key).add(str);
}
return new ArrayList<>(map.values());
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-10-21 23:17:44
class Solution:
def groupStrings(self, strings: List[str]) -> List[List[str]] :
mp = defaultdict(list)
for s in strings :
if s[0] == 'a':
mp[s].append(s)
else:
key = list(s)
for i in range(len(s)):
key[i] = chr( (ord(key[i]) - ord(s[0]) + 26) % 26 + ord('a') )
key = ''.join(key)
mp[key].append(s)
res = []
for mode, sublist in mp.items():
res.append(sublist)
return res
cpp 解法, 执行用时: 0 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-21 23:17:26
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strings) {
vector<vector<string>> res;
unordered_map<string, vector<string>> mp;
for (const auto& str : strings) {
string key(str);
for (auto& ch : key) {
// 注意这里需要加26再求余数26，才能正确处理诸如"ba"这样的情况
ch = (ch - str[0] + 26) % 26 + 'a';
}
// cout << key << " : " << str << endl;
mp[key].push_back(str);
}
for (const auto& m : mp) {
res.push_back(m.second);
}
return res;
}
};
cpp 解法, 执行用时: 20 ms, 内存消耗: 9.6 MB, 提交时间: 2023-10-21 23:17:17
// My Union Find solution, a little bit longer, but provide a different perspective for this problem
class Solution {
public:
vector<vector<string>> groupStrings(vector<string>& strs) {
unordered_map<string, int> strFreq;
for (const auto& str : strs) {
strFreq[str]++;
}
UnionFind uf(strs);
int N = strs.size();
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (strs[i].size() != strs[j].size()) {
continue;
}
if (isShiftedEqual(strs[i], strs[j])) {
uf.unite(strs[i], strs[j]);
}
}
}
map<string, multiset<string>> mp;
uf.buildGroupMap(mp);
vector<vector<string>> res;
for (const auto& m : mp) {
vector<string> group;
for (const auto& str : m.second) {
if (strFreq[str] > 1) {
for (int k = strFreq[str]; k > 0; k--) {
group.push_back(str);
}
} else {
group.push_back(str);
}
}
res.push_back(group);
}
return res;
}
private:
bool isShiftedEqual(string str1, string str2) {
if (str1 == str2) {
return true;
}
auto rightShifted = str1;
for (int i = 0; i < 25; i++) {
for (auto& ch : rightShifted) {
ch = (ch == 'z' ? 'a' : ch + 1);
}
if (str2 == rightShifted) {
return true;
}
}
return false;
}
class UnionFind {
public:
UnionFind(vector<string>& strs) {
for (const auto& str : strs) {
parent[str] = str;
}
}
void buildGroupMap(map<string, multiset<string>>& mp) {
for (const auto& p : parent) {
cout << p.first << endl << "," << p.second<<endl;
for (const auto& iter : p.second) {
cout << "iter=" << iter << endl;
}
auto root = find(p.first);
mp[root].insert(p.first);
}
}
void unite(string x, string y) {
auto px = find(x);
auto py = find(y);
if (px != py) {
parent[px] = py;
}
}
string find(string x) {
if (x == parent[x]) {
return x;
}
return find(parent[x]);
}
private:
unordered_map<string, string> parent;
};
};