1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
//! Valid Anagram [leetcode: valid_anagram](https://leetcode.com/problems/valid-anagram/) //! //! Given two strings *s* and *t* , write a function to determine if *t* is an anagram of *s*. //! //! ***Example1:*** //! //!``` //! Input: s = "anagram", t = "nagaram" //! Output: true //!``` //! //! ***Example2:*** //! //!``` //! Input: s = "rat", t = "car" //! Output: false //!``` //! //! ***Note:*** //! //! You may assume the string contains only lowercase alphabets. //! //! ***Follow up:*** //! //! What if the inputs contain unicode characters? How would you adapt your solution to such case? use std::collections::HashMap; /// # Solutions /// /// # Approach 1: HashMap /// /// * Time complexity: O(n) /// /// * Space complexity: O(1) /// /// ```rust /// use std::collections::HashMap; /// /// pub fn is_anagram(s: String, t: String) -> bool { /// if s.len() != t.len() { return false; } /// /// let mut s_hash = HashMap::new(); /// let mut t_hash = HashMap::new(); /// /// for c in s.chars() { /// *s_hash.entry(c).or_insert(0) += 1; /// } /// /// for c in t.chars() { /// *t_hash.entry(c).or_insert(0) += 1; /// } /// /// for (key, val) in s_hash.iter() { /// if t_hash.get(key) != Some(val) { return false; } /// } /// /// true /// } /// ``` /// /// # Approach 2: Vec Sort /// /// * Time complexity: O(nlogn) /// /// * Space complexity: O(1) /// /// ```rust /// /// pub fn is_anagram(s: String, t: String) -> bool { /// if s.len() != t.len() { return false; } /// /// let mut s_chars: Vec<char> = s.chars().collect(); /// let mut t_chars: Vec<char> = t.chars().collect(); /// /// s_chars.sort_by(|a, b| a.cmp(b)); /// t_chars.sort_by(|a, b| a.cmp(b)); /// /// s_chars == t_chars /// } /// ``` /// pub fn is_anagram(s: String, t: String) -> bool { if s.len() != t.len() { return false; } let mut s_hash = HashMap::new(); let mut t_hash = HashMap::new(); for c in s.chars() { *s_hash.entry(c).or_insert(0) += 1; } for c in t.chars() { *t_hash.entry(c).or_insert(0) += 1; } for (key, val) in s_hash.iter() { if t_hash.get(key) != Some(val) { return false; } } true }