1. Description
You are given an array of positive integers numbers.
A pair of indices (i, j), where i < j, is valid if numbers[i] can be transformed into numbers[j] by swapping at most two digits in one of the numbers. No swap is also allowed.
Return the number of valid pairs.
2. Solution
n = numbers.size()
Time complexity: O(n$^2$)
Space complexity: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| int solution(const vector<int>& numbers) {
unordered_map<string, vector<string>> buckets;
for (int num : numbers) {
string s = to_string(num);
string key = s;
sort(key.begin(), key.end());
buckets[key].push_back(s);
}
int count = 0;
for (auto& [key, values] : buckets) {
int n = values.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int diff = 0;
for (int k = 0; k < values[i].size(); ++k) {
if (values[i][k] != values[j][k]) {
++diff;
}
}
if (diff == 0 || diff == 2) {
++count;
}
}
}
}
return count;
}
|