1061. Lexicographically Smallest Equivalent String
Даны две строки одинаковой длины s1 и s2, а также строка baseStr.
Мы говорим, что символы s1[i] и s2[i] эквивалентны.
Например, если s1 = "abc" и s2 = "cde", то 'a' == 'c', 'b' == 'd' и 'c' == 'e'. Эквивалентные символы следуют правилам рефлексивности, симметрии и транзитивности.
Верните лексикографически наименьшую эквивалентную строку baseStr, используя информацию об эквивалентности из s1 и s2.
Пример:
Input: s1 = "parker", s2 = "morris", baseStr = "parser"
Output: "makkek"
Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is "makkek".
C# решение
сопоставлено/оригиналclass Solution {
void DFS(int src, int[,] adjMatrix, int[] visited, List<int> component, ref int minChar) {
visited[src] = 1;
component.Add(src);
minChar = Math.Min(minChar, src);
for (int i = 0; i < 26; i++) {
if (adjMatrix[src, i] != 0 && visited[i] == 0) {
DFS(i, adjMatrix, visited, component, ref minChar);
}
}
}
public string SmallestEquivalentString(string s1, string s2, string baseStr) {
int[,] adjMatrix = new int[26, 26];
for (int i = 0; i < s1.Length; i++) {
adjMatrix[s1[i] - 'a', s2[i] - 'a'] = 1;
adjMatrix[s2[i] - 'a', s1[i] - 'a'] = 1;
}
int[] mappingChar = new int[26];
for (int i = 0; i < 26; i++) {
mappingChar[i] = i;
}
int[] visited = new int[26];
for (int c = 0; c < 26; c++) {
if (visited[c] == 0) {
List<int> component = new List<int>();
int minChar = 27;
DFS(c, adjMatrix, visited, component, ref minChar);
foreach (int vertex in component) {
mappingChar[vertex] = minChar;
}
}
}
StringBuilder ans = new StringBuilder();
foreach (char c in baseStr) {
ans.Append((char)(mappingChar[c - 'a'] + 'a'));
}
return ans.ToString();
}
}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 {
void DFS(int src, int[,] adjMatrix, vector<int>& visited, List<int> component, ref int minChar) {
visited[src] = 1;
component.push_back(src);
minChar = min(minChar, src);
for (int i = 0; i < 26; i++) {
if (adjMatrix[src, i] != 0 && visited[i] == 0) {
DFS(i, adjMatrix, visited, component, ref minChar);
}
}
}
public string SmallestEquivalentString(string s1, string s2, string baseStr) {
int[,] adjMatrix = new int[26, 26];
for (int i = 0; i < s1.size(); i++) {
adjMatrix[s1[i] - 'a', s2[i] - 'a'] = 1;
adjMatrix[s2[i] - 'a', s1[i] - 'a'] = 1;
}
vector<int>& mappingChar = new int[26];
for (int i = 0; i < 26; i++) {
mappingChar[i] = i;
}
vector<int>& visited = new int[26];
for (int c = 0; c < 26; c++) {
if (visited[c] == 0) {
List<int> component = new List<int>();
int minChar = 27;
DFS(c, adjMatrix, visited, component, ref minChar);
foreach (int vertex in component) {
mappingChar[vertex] = minChar;
}
}
}
StringBuilder ans = new StringBuilder();
foreach (char c in baseStr) {
ans.Append((char)(mappingChar[c - 'a'] + 'a'));
}
return ans.ToString();
}
}Java решение
сопоставлено/оригиналclass Solution {
int minChar;
void DFS(int src, Integer[][] adjMatrix, Integer visited[], List<Integer> component) {
// Mark the character as visited.
visited[src] = 1;
// Add it to the list.
component.add(src);
// Update the minimum character in the component.
minChar = Math.min(minChar, src);
for (int i = 0; i < 26; i++) {
// Perform DFS if the edge exists and the node isn't visited yet.
if (adjMatrix[src][i] != null && visited[i] == null) {
DFS(i, adjMatrix, visited, component);
}
}
}
public String smallestEquivalentString(String s1, String s2, String baseStr) {
// Adjacency matrix to store edges.
Integer adjMatrix[][] = new Integer[26][26];
for (int i = 0; i < s1.length(); i++) {
adjMatrix[s1.charAt(i) - 'a'][s2.charAt(i) - 'a'] = 1;
adjMatrix[s2.charAt(i) - 'a'][s1.charAt(i) - 'a'] = 1;
}
// Array to store the final character mappings.
int mappingChar[] = new int[26];
for (int i = 0; i < 26; i++) {
mappingChar[i] = i;
}
// Array to keep visited nodes during DFS.
Integer visited[] = new Integer[26];
for (int c = 0; c < 26; c++) {
if (visited[c] == null) {
// Store the characters in the current component.
List<Integer> component = new ArrayList<>();
// Variable to store the minimum character in the component.
minChar = 27;
DFS(c, adjMatrix, visited, component);
// Map the characters in the component to the minimum character.
for (int vertex : component) {
mappingChar[vertex] = minChar;
}
}
}
String ans = "";
// Create the answer string.
for (char c : baseStr.toCharArray()) {
ans += (char)(mappingChar[c - 'a'] + 'a');
}
return ans;
}
}Go решение
сопоставлено/оригиналpackage main
func DFS(src int, adjMatrix *[26][26]int, visited *[26]int, component *[]int, minChar *int) {
visited[src] = 1
*component = append(*component, src)
if src < *minChar {
*minChar = src
}
for i := 0; i < 26; i++ {
if adjMatrix[src][i] != 0 && visited[i] == 0 {
DFS(i, adjMatrix, visited, component, minChar)
}
}
}
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
var adjMatrix [26][26]int
for i := 0; i < len(s1); i++ {
adjMatrix[s1[i]-'a'][s2[i]-'a'] = 1
adjMatrix[s2[i]-'a'][s1[i]-'a'] = 1
}
mappingChar := [26]int{}
for i := 0; i < 26; i++ {
mappingChar[i] = i
}
visited := [26]int{}
for c := 0; c < 26; c++ {
if visited[c] == 0 {
component := []int{}
minChar := 27
DFS(c, &adjMatrix, &visited, &component, &minChar)
for _, vertex := range component {
mappingChar[vertex] = minChar
}
}
}
ans := make([]byte, len(baseStr))
for i := range baseStr {
ans[i] = byte(mappingChar[baseStr[i]-'a'] + 'a')
}
return string(ans)
}
func main() {
// Example usage
s1 := "leetcode"
s2 := "programs"
baseStr := "sourcecode"
result := smallestEquivalentString(s1, s2, baseStr)
println(result)
}Algorithm
Создайте матрицу смежности adjMatrix размером 26x26 для хранения рёбер и массив visited для отслеживания посещённых символов.
Итеративно обрабатывайте каждый символ от 0 до 25:
Если символ ещё не посещён, выполните DFS, начиная с этого символа, и сохраните все пройденные символы в векторе component, а минимальный из этих символов в переменной minChar.
Обновите все символы из component до minChar в векторе mappingChar, который хранит окончательное сопоставление символов baseStr.
Пройдите по baseStr и создайте итоговую строку ans, используя символы из mappingChar.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.