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

Rust每日一题(8)—数据结构-字典-valid-anagramleetcode地址给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。注意：若s和t中每个字符出现的次数都相同，则称s和t互为字母异位词。示例1：输入:s=”anag

# <a href="http://www.bwbbw.com/archives/tag/rust" title="View all posts in Rust" target="_blank">Rust</a>每日一题(8)—数据结构-字典-valid-anagram [leetcode地址](https://leetcode.cn/problems/valid-anagram/) 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 **示例 1：** “` 输入: s = “anagram”, t = “nagaram” 输出: true “` **示例 2：** “` 输入: s = “rat”, t = “car” 输出: false “` **难度: 简单** ## 知识点 – HashMap[ Entry 相关API](https://doc.rust-lang.org/std/collections/hash_map/struct.HashMap.html#method.entry) ## 思路 核心还是分析关键操作步骤，主要有两种思路: 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 } } “`

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

难度: 简单

知识点

HashMap Entry 相关API

思路

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

采用两个Hashmap分别存储s和t,最后再遍历一次s的Hashmap确定其字母个数是否一致，算法复杂度O(3N),，空间复杂度O(2N)。

必须考虑减少比较的次数，出发点就是采用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) &lt; 0 {
            return false;
        }
    }
    true
}
}

本文参与区块链开发网，好文好收益，欢迎正在阅读的你也加入。