There is a bi-directional graph with n
vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges
, where each edges[i] = [ui, vi]
denotes a bi-directional edge between vertex ui
and vertex vi
. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself.
You want to determine if there is a valid path that exists from vertex source
to vertex destination
.
Given edges
and the integers n
, source
, and destination
, return true
if there is a valid path from source to destination, or false
otherwise.
Example 1
Example 2
var validPath = function(n, edges, source, destination) {
const parent = [];
for (let i = 0; i < n; i++) {
parent[i] = i;
}
edges.forEach(([node1, node2]) => {
unionParent(parent, node1, node2);
});
const result = findParent(parent, source, destination);
function getParent(parent, x) {
if (parent[x] === x) return x;
return parent[x] = getParent(parent, parent[x]);
}
function unionParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
a < b ? parent[b] = a : parent[a] = b;
}
function findParent(parent, a, b) {
a = getParent(parent, a);
b = getParent(parent, b);
return a === b;
}
return result;
};
You are given two strings of the same length s1
and s2
and a string baseStr
.
We say s1[i]
and s2[i]
are equivalent characters.
s1 = "abc"
and s2 = "cde"
, then we have 'a' == 'c'
, 'b' == 'd'
, and 'c' == 'e'
.Equivalent characters follow the usual rules of any equivalence relation:
'a' == 'a'
.'a' == 'b'
implies 'b' == 'a'
.'a' == 'b'
and 'b' == 'c'
implies 'a' == 'c'
.For example, given the equivalency information from s1 = "abc"
and s2 = "cde"
, "acd"
and "aab"
are equivalent strings of baseStr = "eed"
, and "aab"
is the lexicographically smallest equivalent string of baseStr
.
Return the lexicographically smallest equivalent string of baseStr
by using the equivalency information from s1
and s2
.
Example 1:
Example 2:
Example 3:
1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
s1
, s2
, and baseStr
consist of lowercase English letters./**
* @param {string} s1
* @param {string} s2
* @param {string} baseStr
* @return {string}
*/
var smallestEquivalentString = function(s1, s2, baseStr) {
const uf = new UnionFind();
let result = '';
for (let i = 0; i < s1.length; i++) {
uf.unite(s1[i], s2[i]);
}
for (const letter of baseStr) {
result += uf.find(letter);
}
return result;
};
class UnionFind {
constructor() {
this.parents = new Map();
}
find(a) {
if (!this.parents.has(a)) {
this.parents.set(a, a);
} else if (this.parents.get(a) !== a) {
this.parents.set(a, this.find(this.parents.get(a)));
}
return this.parents.get(a);
}
unite(a, b) {
const rootA = this.find(a);
const rootB = this.find(b);
if (rootA === rootB) {
return;
}
const codeA = rootA.charCodeAt(0);
const codeB = rootB.charCodeAt(0);
if (codeA > codeB) {
this.parents.set(rootA, rootB);
} else {
this.parents.set(rootB, rootA);
}
}
}