LeetCode 249. 移位字符串分组：HashMap键存储逻辑解析

问题描述 #

我们可以通过将字符串中的每个字母移到下一个字母来移位字符串。例如，"abc"可以移位为"bcd"。持续移位字符串可形成序列，比如对"abc"持续移位可得到："abc" -> "bcd" -> ... -> "xyz"。给定字符串数组strings，将所有属于同一移位序列的字符串分组，返回结果顺序不限。

输入示例 #

strings = ["abc","bcd","acef","xyz","az","ba","a","z"]

输出示例 #

[["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]]

Swift实现代码 #

func groupStrings(_ strings: [String]) -> [[String]] {
        
        var dict = [[Int]: [String]]()
        
           for word in strings {         
               var key = [0]
               if word.count > 1 {
                   var a = Array(word)
                   let pivot = Int(a[0].asciiValue!) - 97
               
                   for i in 1..<a.count {
                       let index = (Int(a[i].asciiValue!) - 97 + 26 - pivot) % 26
                       key.append(index)
                   }
               }
               
               if var array = dict[key] {
                   array.append(word)
                   dict[key] = array
               } else {
                   dict[key] = [word]
               }
           }
           return dict.keys.compactMap { dict[$0] }
    }

HashMap键的存储逻辑解析 #

核心逻辑是：同一移位序列的字符串，字符间的相对偏移量完全一致。我们通过生成这个相对偏移量数组作为HashMap的键，就能把同组字符串归到一起。

具体生成规则：

• 对于单个字符的字符串（比如"a"、"z"），直接用[0]作为键。因为单个字符本身就是一个独立的移位序列，所有单个字符都属于同一组。
• 对于长度大于1的字符串：
  1. 取字符串第一个字符，计算它相对于字母'a'的偏移量pivot（比如"abc"的第一个字符是'a'，pivot = 0；"bcd"的第一个字符是'b'，pivot = 1）。
  2. 从第二个字符开始，每个字符计算：(当前字符相对于'a'的偏移量 + 26 - pivot) % 26，将结果依次加入键数组。这个操作把整个字符串"归一化"到以'a'开头的基准形式，确保同一移位序列的字符串生成完全相同的偏移量数组。

举几个对应例子：

• "abc"：第一个字符'a'的pivot=0，第二个字符'b'偏移量1→(1+26-0)%26=1，第三个字符'c'偏移量2→(2+26-0)%26=2，键为[0,1,2]。
• "bcd"：第一个字符'b'的pivot=1，第二个字符'c'偏移量2→(2+26-1)%26=1，第三个字符'd'偏移量3→(3+26-1)%26=2，键同样是[0,1,2]，和"abc"归为一组。
• "az"：第一个字符'a'的pivot=0，第二个字符'z'偏移量25→(25+26-0)%26=25，键为[0,25]。
• "ba"：第一个字符'b'的pivot=1，第二个字符'a'偏移量0→(0+26-1)%26=25，键也是[0,25]，和"az"归为一组。
• "acef"：第一个字符'a'的pivot=0，后续字符'c'偏移2→2、'e'偏移4→4、'f'偏移5→5，键为[0,2,4,5]，单独成组。

HashMap存储示例 #

[[0, 2, 4, 5]: ["acef"], [0, 25]: ["az", "ba"], [0]: ["a", "z"], [0, 1, 2]: ["abc", "bcd", "xyz"]]

内容的提问来源于stack exchange，提问作者Alexander Paul