LC 0249 [M] Group Shifted Strings - ALawliet/algorithms GitHub Wiki

hashmap where the key is the shifted string and the values are the original strings

Your input
["abc","bcd","acef","xyz","az","ba","a","z"]
stdout
(24, 1, 1) (97-99)%26, (98-97)%26, (98-97)%26
(24, 1, 1)
(21, 2, 2, 1)
(24, 1, 1)
(1, 25)
(1, 25)
(0,)
(0,)
Output: ["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"](/ALawliet/algorithms/wiki/"acef"],["a","z"],["abc","bcd","xyz"],["az","ba")

% 26 to normalize the wraparound case

a + 1 = b
z + 1 = a

>>> ord('b')
98
>>> ord('a')
97
>>> ord('z')
122

>>> (ord('b') - ord('a')) % 26
0 r 1
>>> (ord('a') - ord('z')) % 26
25 r 1

---

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        
        for o in strings:
            shifted = ''
            
            for i in range(len(o)):
                x, p = o[i], o[i-1]
                diff = ord(x) - ord(p)
                diff %= 26
                shifted += str(diff)
                
            d[shifted].append(o)
            
        return d.values()

class Solution:
    def groupStrings(self, strings: List[str]) -> List[List[str]]:
        shifted_to_original = defaultdict(list)

        for original in strings:
            shifted = ''

            for i in range(len(original)):
                cur, circ_prev = original[i], original[i-1] # if 'abc', then 'ac', 'ba', 'cb'
                circ_diff = (ord(cur) - ord(circ_prev)) % 26
                shifted += str(circ_diff)

                # print(b, a, circ_diff)
            # print(shifted)

            shifted_to_original[shifted].append(original)

        return shifted_to_original.values()