題目：
給你一個下標從?0?開始的字符串數組?words?。
如果兩個字符串由相同的字符組成，則認為這兩個字符串?相似?。
- 例如，
"abca"?和?"cba"?相似，因為它們都由字符?'a'、'b'、'c'?組成。 - 然而，
"abacba"?和?"bcfd"?不相似，因為它們不是相同字符組成的。
請你找出滿足字符串?words[i]?和?words[j]?相似的下標對?(i, j)?，并返回下標對的數目，其中?0 <= i < j <= words.length - 1?。
示例 1：
輸入：words = ["aba","aabb","abcd","bac","aabc"] 輸出：2 解釋：共有 2 對滿足條件： - i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 組成。 - i = 3 且 j = 4 ：words[3] 和 words[4] 只由字符 'a'、'b' 和 'c' 。
示例 2：
輸入：words = ["aabb","ab","ba"] 輸出：3 解釋：共有 3 對滿足條件： - i = 0 且 j = 1 ：words[0] 和 words[1] 只由字符 'a' 和 'b' 組成。 - i = 0 且 j = 2 ：words[0] 和 words[2] 只由字符 'a' 和 'b' 組成。 - i = 1 且 j = 2 ：words[1] 和 words[2] 只由字符 'a' 和 'b' 組成。
示例 3：
輸入：words = ["nba","cba","dba"] 輸出：0 解釋：不存在滿足條件的下標對，返回 0 。
提示：
1 <= words.length <= 1001 <= words[i].length <= 100words[i]?僅由小寫英文字母組成
解法：
解決思路
-
提取字符集合：
-
對于每個字符串，提取其中包含的字符種類（去重）。
-
例如，
"aba"?的字符集合是?{'a', 'b'}，"aabb"?的字符集合也是?{'a', 'b'}。
-
-
比較字符集合：
-
如果兩個字符串的字符集合相同，則它們相似。
-
例如，
"aba"?和?"aabb"?的字符集合都是?{'a', 'b'}，因此它們相似。
-
-
統計相似對數：
-
對于所有字符串，統計具有相同字符集合的字符串數量。
-
如果有?
k?個字符串具有相同的字符集合，則這些字符串之間可以形成?C(k, 2)?對相似對（即從?k?個字符串中選 2 個的組合數）。
-
實現步驟
-
提取字符集合：
-
對每個字符串，將其字符去重并排序，生成一個唯一的標識符（例如，將字符集合轉換為字符串）。
-
例如，
"aba"?的字符集合是?{'a', 'b'}，可以轉換為字符串?"ab"。
-
-
統計字符集合的出現次數：
-
使用哈希表（
unordered_map）記錄每個字符集合的出現次數。 -
例如，
"ab"?出現 2 次，"abc"?出現 1 次。
-
-
計算相似對數：
-
對于哈希表中的每個字符集合，如果有?
k?個字符串具有相同的字符集合，則這些字符串之間可以形成?k * (k - 1) / 2?對相似對。 -
將所有字符集合的相似對數累加，得到最終結果。
-
代碼實現
class Solution {
public:int similarPairs(vector<string>& words) {unordered_map<string, int> countMap;// 遍歷每個字符串，提取字符集合并統計for (const string& word : words) {string charSet = getCharSet(word);countMap[charSet]++;}int result = 0;// 計算滿足條件的下標對數量for (const auto& pair : countMap) {int k = pair.second;if (k >= 2) {result += k * (k - 1) / 2;}}return result;}private:string getCharSet(const string& word) {vector<char> chars(word.begin(), word.end());sort(chars.begin(), chars.end());chars.erase(unique(chars.begin(), chars.end()), chars.end());return string(chars.begin(), chars.end());}
};代碼詳細解釋
-
getCharSet?函數：-
輸入：一個字符串?
word。 -
輸出：該字符串的字符集合（去重并排序后的字符串）。
-
實現步驟：
-
將字符串轉換為字符數組?
chars。 -
對字符數組排序（
sort）。 -
去重（
unique?和?erase）。 -
將字符數組轉換為字符串并返回。
-
示例：
-
輸入：
"aba" -
輸出：
"ab"
-
-
similarPairs?函數：-
輸入：字符串數組?
words。 -
輸出：滿足條件的下標對數量。
-
實現步驟：
-
遍歷每個字符串，調用?
getCharSet?獲取字符集合。 -
使用哈希表?
countMap?統計每個字符集合的出現次數。 -
遍歷哈希表，計算每個字符集合的相似對數，并累加到結果中。
-
示例：
-
輸入：
["aba", "aabb", "abcd", "bac", "aabc"] -
哈希表內容：
{"ab": 2, "abcd": 1, "abc": 2} -
計算結果：
C(2, 2) + C(2, 2) = 1 + 1 = 2
-
復雜度分析
-
時間復雜度：
-
提取字符集合：對于每個字符串，排序和去重的復雜度為?
O(m log m)，其中?m?是字符串的平均長度。 -
統計哈希表：遍歷所有字符串的復雜度為?
O(n)，其中?n?是字符串的數量。 -
計算相似對數：遍歷哈希表的復雜度為?
O(n)。 -
總時間復雜度：
O(n * m log m)。
-
-
空間復雜度：
-
哈希表?
countMap?的空間復雜度為?O(n)。 -
字符集合的空間復雜度為?
O(m)。 -
總空間復雜度：
O(n * m)。
-
示例運行
示例 1：
輸入：words = ["aba", "aabb", "abcd", "bac", "aabc"]
-
提取字符集合：
-
"aba"?->?"ab" -
"aabb"?->?"ab" -
"abcd"?->?"abcd" -
"bac"?->?"abc" -
"aabc"?->?"abc"
-
-
統計哈希表：
-
{"ab": 2, "abcd": 1, "abc": 2}
-
-
計算相似對數：
-
"ab"?出現 2 次 ->?C(2, 2) = 1 -
"abc"?出現 2 次 ->?C(2, 2) = 1 -
總相似對數：
1 + 1 = 2
-
輸出：2
示例 2：
輸入：words = ["aabb", "ab", "ba"]
-
提取字符集合：
-
"aabb"?->?"ab" -
"ab"?->?"ab" -
"ba"?->?"ab"
-
-
統計哈希表：
-
{"ab": 3}
-
-
計算相似對數：
-
"ab"?出現 3 次 ->?C(3, 2) = 3 -
總相似對數：
3
-
輸出：3
示例 3：
輸入：words = ["nba", "cba", "dba"]
-
提取字符集合：
-
"nba"?->?"abn" -
"cba"?->?"abc" -
"dba"?->?"abd"
-
-
統計哈希表：
-
{"abn": 1, "abc": 1, "abd": 1}
-
-
計算相似對數：
-
每個字符集合只出現 1 次，無法形成相似對。
-
總相似對數：
0
-
輸出：0
總結
通過提取字符集合、統計哈希表，并計算組合數，我們可以高效地解決這個問題。代碼的時間復雜度和空間復雜度都在合理范圍內，能夠處理題目中的最大輸入規模。
