最大字符串配对数目

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。

题目描述

给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。

如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：

字符串 words[i] 等于 words[j] 的反转字符串。
0 <= i < j < words.length
请你返回数组 words 中的 最大 匹配数目。

注意，每个字符串最多匹配一次。

示例 1：

输入：words = ["cd","ac","dc","ca","zz"]
输出：2
解释：在此示例中，我们可以通过以下方式匹配 2 对字符串：
- 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 "dc" 并且等于 words[2]。
- 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 "ca" 并且等于 words[3]。
可以证明最多匹配数目是 2 。

示例 2：

输入：words = ["ab","ba","cc"]
输出：1
解释：在此示例中，我们可以通过以下方式匹配 1 对字符串：
- 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 "ab" 与 words[0] 相等。
可以证明最多匹配数目是 1 。

示例 3：

输入：words = ["aa","ab"]
输出：0
解释：这个例子中，无法匹配任何字符串。

提示：

• 1 <= words.length <= 50
• words[i].length == 2
• words 包含的字符串互不相同。
• words[i] 只包含小写英文字母。

解题思路

题目其实就是要找到数组中的各元素与其他元素的反转字符串相同的个数总和，那么我们首先需要写一个可以反转字符串的方法

反转字符串

最简单的就是从后往前遍历，重新拼接一个字符串返回既可：

const reverse = (word) => {
    let res = '';
    for(let i = word.length - 1; i >= 0; i--) res += word[i];
    return res;
}

还有更简便的方法便是利用数组的reverse方法，可以将数组反转。我们先使用split方法将字符串转为数组，再利用数组的reverse方法将数组反转，最后通过join方法将数组拼接为字符串即可：

const reverse = (word) => {
    return word.split('').reverse().join('');
}

二次遍历计算

我们可以直接进行二次遍历，判断当前元素后面元素的反转字符串与当前元素相等的数量。

/**
 * @param {string[]} words
 * @return {number}
 */
var maximumNumberOfStringPairs = function(words) {
    let cnt = 0;
    for(let i = 0; i < words.length; i++){
        const tmpWord = words[i].split('').reverse().join('');
        for(let j = i + 1; j < words.length; j++){
            if(tmpWord === words[j]) cnt++;
        }
    }
    return cnt;
};

一次遍历计算

当然，我们还有更简便的方法，可以通过一次遍历，使用一个哈希表来保存遍历过的元素的反转字符串，往后遍历的时候判断哈希表中有没有和自己相同的元素即可。

/**
 * @param {string[]} words
 * @return {number}
 */
var maximumNumberOfStringPairs = function(words) {
    let cnt = 0;
    const map = {};
    const reverse = (word) => {
        return word.split('').reverse().join('');
    }
    for(let i = 0; i < words.length; i++){
        if(map[words[i]]) cnt++;
        map[reverse(words[i])] = true;
    }
    return cnt;
};

公众号

关注公众号『前端也能这么有趣』，获取更多有趣内容。

说在后面

🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。