最大字符串配对数目

You are given a 0-indexed array words consisting of distinct strings.

The string words[i] can be paired with the string words[j] if:

• The string words[i] is equal to the reversed string of words[j].
• 0 <= i < j < words.length.

Return the maximum number of pairs that can be formed from the array words.

Note that each string can belong in at most one pair.

 

Example 1:

Input: words = ["cd","ac","dc","ca","zz"]
Output: 2
Explanation: In this example, we can form 2 pair of strings in the following way:
- We pair the 0th string with the 2nd string, as the reversed string of word[0] is "dc" and is equal to words[2].
- We pair the 1st string with the 3rd string, as the reversed string of word[1] is "ca" and is equal to words[3].
It can be proven that 2 is the maximum number of pairs that can be formed.

Example 2:

Input: words = ["ab","ba","cc"]
Output: 1
Explanation: In this example, we can form 1 pair of strings in the following way:
- We pair the 0th string with the 1st string, as the reversed string of words[1] is "ab" and is equal to words[0].
It can be proven that 1 is the maximum number of pairs that can be formed.

Example 3:

Input: words = ["aa","ab"]
Output: 0
Explanation: In this example, we are unable to form any pair of strings.

 

Constraints:

• 1 <= words.length <= 50
• words[i].length == 2
• words consists of distinct strings.
• words[i] contains only lowercase English letters.

/*
 * 思路：
 * 1. 使用一个HashSet来保存已访问的字符串。
 * 2. 使用流来处理数组words。
 * 3. 对于每个字符串word，生成它的反转字符串revWord。
 * 4. 检查revWord是否在已访问的字符串集合中，如果在，则匹配成功，增加计数，并从集合中移除revWord。
 * 5. 如果revWord不在集合中，则将当前word添加到集合中。
 * 6. 使用原子整数来保存计数并返回最终结果。
 */
import java.util.HashSet;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.Stream;

public class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        HashSet<String> set = new HashSet<>();
        AtomicInteger count = new AtomicInteger(0);
        Stream.of(words).forEach(word -> {
            String revWord = new StringBuilder(word).reverse().toString();
            if (set.contains(revWord)) {
                count.incrementAndGet();
                set.remove(revWord);
            } else {
                set.add(word);
            }
        });
        return count.get();
    }
}

此题解采用了哈希集合来记录已经遍历过的字符串。对每个字符串，首先检查其反转字符串是否已经存在于集合中，如果存在，则说明找到了一对可以匹配的字符串，因此结果计数加一。如果不存在，则将当前字符串加入到集合中，以便后续字符串进行匹配检查。这种方法利用了集合的高效查找特性，简化了匹配过程。

O(n)

O(n)