49. Group Anagrams Medium

1/**
2 * [49] Group Anagrams
3 *
4 * Given an array of strings strs, group the anagrams together. You can return the answer in any order.
5 * An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
6 *  
7 * Example 1:
8 * Input: strs = ["eat","tea","tan","ate","nat","bat"]
9 * Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
10 * Example 2:
11 * Input: strs = [""]
12 * Output: [[""]]
13 * Example 3:
14 * Input: strs = ["a"]
15 * Output: [["a"]]
16 *  
17 * Constraints:
18 *
19 * 1 <= strs.length <= 10^4
20 * 0 <= strs[i].length <= 100
21 * strs[i] consists of lowercase English letters.
22 *
23 */
24pub struct Solution {}
25
26// problem: https://leetcode.com/problems/group-anagrams/
27// discuss: https://leetcode.com/problems/group-anagrams/discuss/?currentPage=1&orderBy=most_votes&query=
28
29// submission codes start here
30use std::collections::HashMap;
31impl Solution {
32    pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
33        let mut map: HashMap<String, i32> = HashMap::new();
34        let mut result = vec![];
35        for str in strs {
36            let key = Self::key(&str);
37            let m = map.get(&key);
38            match m {
39                None => {
40                    map.insert(key, result.len() as i32);
41                    result.push(vec![str]);
42                },
43                Some(f) => {
44                    result[*f as usize].push(str);
45                }
46            }
47        }
48        result
49    }
50
51    fn key(str: &String) -> String {
52        let mut result = vec![0; 26];
53        for c in str.chars() {
54            result[c as usize - 'a' as usize] += 1;
55        }
56
57        let mut r = String::new();
58        result.iter().for_each(|x| {
59            r.push_str(&(*x).to_string());
60            r.push(',')
61        });
62        r
63    }
64}
65
66// submission codes end
67
68#[cfg(test)]
69mod tests {
70    use super::*;
71
72    #[test]
73    fn test_49() {
74        println!("Got {:#?}", Solution::group_anagrams(vec![
75            "eat".to_string(),
76            "tea".to_string(),
77            "tan".to_string(),
78            "ate".to_string(),
79            "nat".to_string(),
80            "bat".to_string()
81        ]));
82    }
83}
84