249. Group Shifted Strings

leetcode medium

#array#csharp#graph#hash-table#leetcode#medium#string

Task

Выполните следующие операции сдвига на строке:

Правый сдвиг: замените каждую букву следующей буквой английского алфавита, где 'z' заменяется на 'a'. Например, "abc" можно сдвинуть вправо на "bcd" или "xyz" можно сдвинуть вправо на "yza".

Левый сдвиг: замените каждую букву предыдущей буквой английского алфавита, где 'a' заменяется на 'z'. Например, "bcd" можно сдвинуть влево на "abc" или "yza" можно сдвинуть влево на "xyz".

Мы можем продолжать сдвигать строку в обоих направлениях, чтобы сформировать бесконечную последовательность сдвигов.

Например, сдвиньте "abc", чтобы сформировать последовательность: ... <-> "abc" <-> "bcd" <-> ... <-> "xyz" <-> "yza" <-> .... <-> "zab" <-> "abc" <-> ...

Вам дан массив строк strings, сгруппируйте все strings[i], которые принадлежат одной и той же последовательности сдвигов. Ответ можно вернуть в любом порядке.

Пример

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

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

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
    private char ShiftLetter(char letter, int shift) {
        return (char) ((letter - shift + 26) % 26 + 'a');
    }
    
    private string GetHash(string s) {
        int shift = s[0];
        StringBuilder hashKey = new StringBuilder();
        
        foreach (char letter in s) {
            hashKey.Append(ShiftLetter(letter, shift));
        }
        
        return hashKey.ToString();
    }
    
    public IList<IList<string>> GroupStrings(IList<string> strings) {
        var mapHashToList = new Dictionary<string, IList<string>>();
        
        foreach (string str in strings) {
            string hashKey = GetHash(str);
            if (!mapHashToList.ContainsKey(hashKey)) {
                mapHashToList[hashKey] = new List<string>();
            }
            mapHashToList[hashKey].Add(str);
        }
        
        var groups = new List<IList<string>>();
        foreach (var pair in mapHashToList) {
            groups.Add(pair.Value);
        }
        
        return groups;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private char ShiftLetter(char letter, int shift) {
        return (char) ((letter - shift + 26) % 26 + 'a');
    }
    
    private string GetHash(string s) {
        int shift = s[0];
        StringBuilder hashKey = new StringBuilder();
        
        foreach (char letter in s) {
            hashKey.Append(ShiftLetter(letter, shift));
        }
        
        return hashKey.ToString();
    }
    
    public IList<vector<string>> GroupStrings(vector<string> strings) {
        var mapHashToList = new unordered_map<string, vector<string>>();
        
        foreach (string str in strings) {
            string hashKey = GetHash(str);
            if (!mapHashToList.count(hashKey)) {
                mapHashToList[hashKey] = new List<string>();
            }
            mapHashToList[hashKey].push_back(str);
        }
        
        var groups = new List<vector<string>>();
        foreach (var pair in mapHashToList) {
            groups.push_back(pair.Value);
        }
        
        return groups;
    }
}

Java solution

matched/original

class Solution {
    private char shiftLetter(char letter, int shift) {
        return (char) ((letter - shift + 26) % 26 + 'a');
    }
    
    private String getHash(String s) {
        int shift = s.charAt(0);
        StringBuilder hashKey = new StringBuilder();
        
        for (char letter : s.toCharArray()) {
            hashKey.append(shiftLetter(letter, shift));
        }
        
        return hashKey.toString();
    }
    
    public List<List<String>> groupStrings(String[] strings) {
        Map<String, List<String>> mapHashToList = new HashMap<>();
        
        for (String str : strings) {
            String hashKey = getHash(str);
            mapHashToList.computeIfAbsent(hashKey, k -> new ArrayList<>()).add(str);
        }
        
        return new ArrayList<>(mapHashToList.values());
    }
}

JavaScript solution

matched/original

class Solution {
    shiftLetter(letter, shift) {
        return String.fromCharCode((letter.charCodeAt(0) - shift + 26) % 26 + 'a'.charCodeAt(0));
    }

    getHash(s) {
        const shift = s.charCodeAt(0);
        return Array.from(s, letter => this.shiftLetter(letter, shift)).join('');
    }

    groupStrings(strings) {
        const mapHashToList = new Map();

        for (const str of strings) {
            const hashKey = this.getHash(str);
            if (!mapHashToList.has(hashKey)) {
                mapHashToList.set(hashKey, []);
            }
            mapHashToList.get(hashKey).push(str);
        }

        return Array.from(mapHashToList.values());
    }
}

Python solution

matched/original

class Solution:
    def shiftLetter(self, letter, shift):
        return chr((ord(letter) - shift + 26) % 26 + ord('a'))
    
    def getHash(self, s):
        shift = ord(s[0])
        hashKey = ''.join(self.shiftLetter(letter, shift) for letter in s)
        return hashKey
    
    def groupStrings(self, strings):
        mapHashToList = defaultdict(list)
        
        for str in strings:
            hashKey = self.getHash(str)
            mapHashToList[hashKey].append(str)
        
        return list(mapHashToList.values())

Go solution

matched/original

package main

import (
    "fmt"
    "strings"
)

func shiftLetter(letter byte, shift int) byte {
    return (letter - byte(shift) + 26) % 26 + 'a'
}

func getHash(s string) string {
    shift := s[0] - 'a'
    var hashKey strings.Builder
    
    for i := 0; i < len(s); i++ {
        hashKey.WriteByte(shiftLetter(s[i], int(shift)))
    }
    
    return hashKey.String()
}

func groupStrings(strings []string) [][]string {
    mapHashToList := make(map[string][]string)
    
    for _, str := range strings {
        hashKey := getHash(str)
        mapHashToList[hashKey] = append(mapHashToList[hashKey], str)
    }
    
    groups := [][]string{}
    for _, v := range mapHashToList {
        groups = append(groups, v)
    }
    
    return groups
}

func main() {
    strings := []string{"abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"}
    result := groupStrings(strings)
    fmt.Println(result)
}

Explanation

Algorithm

1️⃣

Переберите строки, и для каждой строки найдите ее хэш-значение, сдвигая все символы так, чтобы строка начиналась с 'a'. Значение сдвига равно позиции первого символа строки, и каждый символ сдвигается на это значение с учетом модуля 26.

2️⃣

Сопоставьте оригинальную строку с найденным хэш-значением в карте mapHashToList, добавляя оригинальную строку в список, соответствующий ее хэш-значению.

3️⃣

Переберите mapHashToList и сохраните список для каждого ключа в карте в массив ответа groups.

😎