893. Groups of Special-Equivalent Strings

LeetCode medium оригинал: C# #array #csharp #hash-table #leetcode #medium #sort #string

LeetCode Static

Вам дан массив строк одинаковой длины words. За один ход вы можете поменять местами любые два четных или любые два нечетных символа строки words[i]. Две строки words[i] и words[j] являются специально-эквивалентными, если после любого количества ходов words[i] == words[j].

Например, words[i] = "zzxy" и words[j] = "xyzz" являются специально-эквивалентными, потому что мы можем делать ходы "zzxy" -> "xzzy" -> "xyzz". Группа специально-эквивалентных строк из слов - это непустое подмножество слов, такое, что: каждая пара строк в группе специально-эквивалентна, и группа имеет максимально возможный размер (т.е, не существует строки words[i], не входящей в группу, такой, что words[i] является специально-эквивалентной каждой строке в группе). Верните количество групп специально-эквивалентных строк из слов.

Пример:

Input: words = ["abcd","cdab","cbad","xyzz","zzxy","zzyx"]

Output: 3

C# решение

сопоставлено/оригинал

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public int NumSpecialEquivGroups(string[] words) {
        var uniqueForms = new HashSet<string>();
        
        foreach (var word in words) {
            var evenChars = word.Where((c, i) => i % 2 == 0).OrderBy(c => c).ToArray();
            var oddChars = word.Where((c, i) => i % 2 != 0).OrderBy(c => c).ToArray();
            var canonicalForm = new string(evenChars) + new string(oddChars);
            uniqueForms.Add(canonicalForm);
        }
        
        return uniqueForms.Count;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#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:
    public int NumSpecialEquivGroups(vector<string> words) {
        var uniqueForms = new HashSet<string>();
        
        foreach (var word in words) {
            var evenChars = word.Where((c, i) => i % 2 == 0).OrderBy(c => c).ToArray();
            var oddChars = word.Where((c, i) => i % 2 != 0).OrderBy(c => c).ToArray();
            var canonicalForm = new string(evenChars) + new string(oddChars);
            uniqueForms.push_back(canonicalForm);
        }
        
        return uniqueForms.size();
    }
}

Java решение

сопоставлено/оригинал

import java.util.*;

class Solution {
    public int numSpecialEquivGroups(String[] words) {
        Set<String> uniqueForms = new HashSet<>();
        
        for (String word : words) {
            char[] evenChars = new char[(word.length() + 1) / 2];
            char[] oddChars = new char[word.length() / 2];
            
            for (int i = 0; i < word.length(); i++) {
                if (i % 2 == 0) {
                    evenChars[i / 2] = word.charAt(i);
                } else {
                    oddChars[i / 2] = word.charAt(i);
                }
            }
            
            Arrays.sort(evenChars);
            Arrays.sort(oddChars);
            String canonicalForm = new String(evenChars) + new String(oddChars);
            uniqueForms.add(canonicalForm);
        }
        
        return uniqueForms.size();
    }

JavaScript решение

сопоставлено/оригинал

var numSpecialEquivGroups = function(words) {
    const uniqueForms = new Set();
    
    for (let word of words) {
        const evenChars = word.split('').filter((_, i) => i % 2 === 0).sort().join('');
        const oddChars = word.split('').filter((_, i) => i % 2 !== 0).sort().join('');
        const canonicalForm = evenChars + oddChars;
        uniqueForms.add(canonicalForm);
    }
    
    return uniqueForms.size;

Go решение

сопоставлено/оригинал

package main

import (
  "sort"
  "strings"
)

func numSpecialEquivGroups(words []string) int {
  uniqueForms := make(map[string]struct{})
  
  for _, word := range words {
    evenChars := []rune{}
    oddChars := []rune{}
    
    for i, c := range word {
      if i % 2 == 0 {
        evenChars = append(evenChars, c)
      } else {
        oddChars = append(oddChars, c)
      }
    }
    
    sort.Slice(evenChars, func(i, j int) bool { return evenChars[i] < evenChars[j] })
    sort.Slice(oddChars, func(i, j int) bool { return oddChars[i] < oddChars[j] })
    canonicalForm := string(evenChars) + string(oddChars)
    uniqueForms[canonicalForm] = struct{}{}
  }
  
  return len(uniqueForms)
}

Algorithm

Для каждой строки в массиве words создать два новых списка: один из символов на четных позициях, другой из символов на нечетных позициях. Отсортировать оба списка и объединить их в одну строку, которая будет представлять каноническую форму строки.

Использовать множество, чтобы хранить все уникальные канонические формы строк.

Размер множества будет равен количеству групп специально-эквивалентных строк.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.