思路
利用hashMap存储每个字符串的反转字符的出现次数,然后进行逐一比较
解题方法
for(int j=words[i].length()-1;j>=0;j–){//反转字符串
s=s+words[i].charAt(j);
}
注意:对于xx型字符串与xy型字符串比较方式不同
时间复杂度: O(n)
空间复杂度,: O(n)
Code
class Solution {
public static int maximumNumberOfStringPairs(String[] words) {
int ans=0;
HashMap<String,Integer> hashMap=new HashMap<>();
for(int i=0;i<words.length;i++){
String s="";
for(int j=words[i].length()-1;j>=0;j--){
s=s+words[i].charAt(j);
}
hashMap.put(s,hashMap.getOrDefault(s,0)+1);
}
for(int i=0;i<words.length;i++) {
if (words[i].charAt(0) == words[i].charAt(1)) {//xx型字符串
if (hashMap.getOrDefault(words[i], -1) > 1) {
ans++;
hashMap.put(words[i], hashMap.get(words[i]) - 1);
}
} else { //xy型字符串
if (hashMap.getOrDefault(words[i], -1) >= 1) {
ans++;
hashMap.put(words[i], hashMap.get(words[i]) - 1);
}
}
}
return ans/2;
}
}
官方题解
class Solution {
public int maximumNumberOfStringPairs(String[] words) {
int n = words.length;
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (words[i].charAt(0) == words[j].charAt(1) && words[i].charAt(1) == words[j].charAt(0)) {
++ans;
}
}
}
return ans;
}
}
作者:力扣官方题解