2024.1.17——最大字符串配对数目

题目来源

[力扣每日一题；题序：2744](https://leetcode.cn/problems/find-maximum-number-of-string-pairs/description/?envType=daily-question&envId=2024-01-17

我的题解

方法一 暴力法（双重循环）

采用双重循环，判断两个字符串是否符合反转匹配。因为字符串的长度只有2个字符，所以判断是否反转比较简单。

时间复杂度：O($n^2$)
空间复杂度：O(1)

public int maximumNumberOfStringPairs(String[] words) {
     List<String> list=new ArrayList<>();
     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;
 }

方法二 集合+反转字符串

使用一个集合存放反转的字符，若遍历到后续的字符在集合中存在，则将其移除，若不存在则加入。最终返回（原字符串数组的长度-集合的大小）/2。除2是因为匹配需要消耗2个字符串。

时间复杂度：O($n^2$)。反转字符串的时间复杂度也是O(n)
空间复杂度：O(2)。单个字符串的长度。

public int maximumNumberOfStringPairs(String[] words) {
   List<String> list=new ArrayList<>();
    for(int i=0;i<words.length;i++){
        StringBuilder s=new StringBuilder(words[i]).reverse();
        if(list.contains(words[i])){
            list.remove(words[i]);
        }else{
            list.add(s.toString());
        }
    }
    return (words.length-list.size())/2;
}

方法三 哈希表+自定义哈希函数

使用哈希表存储每个字符串的哈希值（因为只有两个字符，所以使用100a+b作为哈希函数）。

时间复杂度：O(n)
空间复杂度：O(n)

 public int maximumNumberOfStringPairs(String[] words) {
  int n = words.length;
    int ans = 0;
    Set<Integer> seen = new HashSet<Integer>();
    for (int i = 0; i < n; ++i) {
        if (seen.contains(words[i].charAt(1) * 100 + words[i].charAt(0))) {
            ++ans;
        }
        seen.add(words[i].charAt(0) * 100 + words[i].charAt(1));
    }
    return ans;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~