Rust每日一题(8)---数据结构-字典-valid-anagram

Rust每日一题(8)---数据结构-字典-valid-anagram

Rust每日一题(8)---数据结构-字典-valid-anagram

leetcode地址 给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

难度: 简单

知识点

思路

核心还是分析关键操作步骤,主要有两种思路:

  1. 采用两个Hashmap分别存储s和t,最后再遍历一次s的Hashmap确定其字母个数是否一致,算法复杂度O(3N),,空间复杂度O(2N)。
  2. 必须考虑减少比较的次数,出发点就是采用Hashmap只存储s中每个字母的count,然后遍历t的字母,每次将count-1,一旦count小于0,就返回负数,算法复杂度O(2*N),且只用了一个Hashmap,空间复杂度O(N)。
    use std::collections::HashMap;
    impl Solution {
    pub fn is_anagram(s: String, t: String) -> bool {
        if s.len() != t.len() {
            return false;
        }
        let mut s_map = HashMap::new();
        for c in s.chars() {
            let count = s_map.entry(c).or_insert(0);
            *count += 1;
        }
        for c in t.chars() {
            let count = s_map.entry(c).or_insert(0);
            *count -= 1;
            if(*count) < 0 {
                return false;
            }
        }
        true
    }
    }

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2022-09-02 00:40
  • 阅读 ( 222 )
  • 学分 ( 1 )
  • 分类:Rust

0 条评论

请先 登录 后评论
Johnathan
Johnathan

PhD

24 篇文章, 1335 学分