算法每日一题: 最大字符串匹配数目 | 哈希 | 哈希表 | 题意分析

发布时间:2024年01月18日

hello 大家好,我是星恒
今天给大家带来的是hash,思路有好几种,需要注意的是这中简单的题目需要仔细看条件,往往他们有对应题目的特殊的解法

题目:leetcode 2744
给你一个下标从 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] 只包含小写英文字母。

分析:
思路1:

  • 将字符串反转
  • 然后将字符串存入hash中
  • 反转字符串,将反转后的字符串存入hash中(如果存在,就+1)(如果反转后和之前一样,就不+1)
  • 遍历hash,如果hash值是2的数,就是有反转串的人,计数
  • 由于每对反转串都会被计数两次,所以最后要除以2

思路2:
直接遍历,如果相同,就count + 1
如何避免多次计数,只要第二次循环j从第一次循环i开始循环就可以了

思路3:
哈希表
对于比较方便得到反转字符串的语言,我们可以在哈希集合中存储字符串本身;对于其它语言,我们可以存储字符串的哈希值,改为判断 words[i]\textit{words}[i]words[i] 的反转字符串的哈希值是否存在。哈希值需要保证不会冲突,本题中字符串的长度为 222 并且只包含小写字母,因此可以使用 100a+b100a + b100a+b 作为哈希值,其中 aaa 和 bbb 分别是两个字符的 ASCII\text{ASCII}ASCII 值。

题解:
我的题解:

class Solution {
    public int maximumNumberOfStringPairs(String[] words) {
        Map<String, Integer> maps = new HashMap<>();
        int count = 0; 

        for (int i = 0; i < words.length; i++) {
            maps.put(words[i], 1);
            words[i] = reverse(words[i]);
        }

        for (int i = 0; i < words.length; i++) {
            if (!words[i].equals(reverse(words[i]))) {
                maps.put(words[i], maps.getOrDefault(words[i], 0) + 1);
            }
        }

        for (Map.Entry<String, Integer> map: maps.entrySet()) {
            if (map.getValue() == 2) {
                count++;
            }
        }

        return count/2;
    }

    public String reverse(String s) {
        char[] arr = s.toCharArray();
        int left = 0, right = s.length() - 1;

        while(left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;

            left++;
            right--;
        }

        return new String(arr);
    }
}

知识点:

  • getOrDefault()
  • 字符串反转:转字符数组 - 双指针遍历交换 - 字符数组转为字符串
  • Map遍历:遍历项的类型:Map.Entry
  • 字符串比较值大小 equals()

官方题解1:

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;
    }
}

官方题解2:哈希

class Solution {
    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;
    }
}
文章来源:https://blog.csdn.net/m0_61780691/article/details/135663086
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。