【2022-11-11每日一题】1704. 判断字符串的两半是否相似[Easy]

2022-11-11每日一题：1704. 判断字符串的两半是否相似

难度：Easy

标签：字符串 、 计数

给你一个偶数长度的字符串 s 。将其拆分成长度相同的两半，前一半为 a ，后一半为 b 。

两个字符串 相似 的前提是它们都含有相同数目的元音（'a'，'e'，'i'，'o'，'u'，'A'，'E'，'I'，'O'，'U'）。注意，s 可能同时含有大写和小写字母。

如果 a 和 b 相似，返回 true ；否则，返回 false 。

示例 1：

输入：s = "book"
输出：true
解释：a = "bo" 且 b = "ok" 。a 中有 1 个元音，b 也有 1 个元音。所以，a 和 b 相似。

示例 2：

输入：s = "textbook"
输出：false
解释：a = "text" 且 b = "book" 。a 中有 1 个元音，b 中有 2 个元音。因此，a 和 b 不相似。
注意，元音 o 在 b 中出现两次，记为 2 个。

提示：

• 2 <= s.length <= 1000
• s.length 是偶数
• s 由 大写和小写 字母组成

方法一：直接遍历+基数

写法一

func halvesAreAlike(s string) bool {
    cnt := 0
    // 计算前半部分
    for _, c := range s[:len(s)/2] {
        if strings.ContainsRune("aeiouAEIOU", c) {
            cnt++
        }
    }
    // 计算后半部分
 	for _, c := range s[len(s)/2:] {
        if strings.ContainsRune("aeiouAEIOU", c) {
            cnt--
        }
    }
    return cnt==0
}

写法二

func halvesAreAlike(s string) bool {
    ht := make(map[rune]struct{}, 10)
    for _, c := range "aeiouAEIOU" {
        ht[c] = struct{}{}
    }
    cnt := 0
    // 计算前半部分
    for _, c := range s[:len(s)/2] {
        if _, ok := ht[c]; ok {
            cnt++
        }
    }
    // 计算后半部分
 	for _, c := range s[len(s)/2:] {
        if _, ok := ht[c]; ok {
            cnt--
        }
    }
    return cnt==0
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串 s 的长度。
• 空间复杂度：O(1) 或者 O(C)， C为元音大小写字母个数。

LeetCode题库地址

• https://leetcode.cn/problems/determine-if-string-halves-are-alike