影響網(wǎng)站速度嗎網(wǎng)站優(yōu)化哪家好
問題背景
給你一個(gè)下標(biāo)從 0 0 0 開始的字符串?dāng)?shù)組 w o r d s words words。
如果兩個(gè)字符串由相同的字符組成，則認(rèn)為這兩個(gè)字符串 相似 。
- 例如，“abca” 和 “cba” 相似，因?yàn)樗鼈兌加勺址?‘a(chǎn)’、‘b’、‘c’ 組成。
- 然而，“abacba” 和 “bcfd” 不相似，因?yàn)樗鼈儾皇窍嗤址M成的。
請你找出滿足字符串 w o r d s [ i ] words[i] words[i] 和 w o r d s [ j ] words[j] words[j] 相似的下標(biāo)對 ( i , j ) (i, j) (i,j)，并返回下標(biāo)對的數(shù)目，其中 0 ≤ i < j ≤ w o r d s . l e n g t h ? 1 0 \le i \lt j \le words.length - 1 0≤i<j≤words.length?1。
數(shù)據(jù)約束
- 1 ≤ w o r d s . l e n g t h ≤ 100 1 \le words.length \le 100 1≤words.length≤100
- 1 ≤ w o r d s [ i ] . l e n g t h ≤ 100 1 \le words[i].length \le 100 1≤words[i].length≤100
- w o r d s [ i ] words[i] words[i] 僅由小寫英文字母組成
解題過程
想到了字符串映射和字符串哈希，沒想到用位運(yùn)算來進(jìn)行壓縮存儲(chǔ)。統(tǒng)計(jì)數(shù)量的做法，參考 好數(shù)對數(shù)目 就可以了。
具體實(shí)現(xiàn)
class Solution {public int similarPairs(String[] words) {Map<Integer, Integer> count = new HashMap<>();int res = 0;for (String word : words) {int mask = 0;for (char c : word.toCharArray()) {mask |= 1 << (c - 'a');}int cur = count.getOrDefault(mask, 0);res += cur;count.put(mask, cur + 1);}return res;}
}